Discuss all kind of algorithms and data structures from their mathematical and programming sides.
Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard
I know that Merge sort uses the Divide & Conquer approach. Then is it faster to use an array than a list when using this algorithm? I mean, arrays take Theta(1) time asymptotically to divide while a list with n-elements take Theta(n) time. It may appear obvious when lists are so much slower to divide, but maybe lists are faster than arrays in the conquer or combine step?
Thankful for help.
- Posts: 1
- Joined: Sat Aug 08, 2009 4:11 pm
I was going to make some observations, but it turns out that the section called "Analysis" of the Wikipedia page on merge sort already covers them, and then some. I suggest you read it carefully.
- Posts: 5185
- Joined: Mon Sep 22, 2003 4:57 pm
- Location: NY, USA
Return to Algorithms & Data Structures
Who is online
Users browsing this forum: No registered users and 0 guests