13
$\begingroup$

Merge sort

So merge sort is a divide and conquer algorithm. While I was looking at the above diagram, I was thinking if it was possible to basically bypass all the divide steps.

If you iterated over the original array while jumping by two, you could get the elements at at index i and i+1 and put them into their own sorted arrays. Once you have all these sub-arrays ([7,14], [3,12], [9,11] and [2,6] as shown in the diagram), you could simply proceed with the normal merge routine to get a sorted array.

Is iterating through the array and immediately generating the required sub-arrays less efficient than performing the divide steps in their entirety?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
29
$\begingroup$

The confusion arises from difference between the conceptual description of the algorithm, and its implementation.

Logically merge sort is described as splitting up the array into smaller arrays, and then merging them back together. However, "splitting the array" doesn't imply "creating an entirely new array in memory", or anything like that - it could be implemented in code as

/*
 * Note: array is now split into  [0..n) and [n..N)
 */

i.e. no actual work takes place, and the "splitting" is purely conceptual. So what you suggest certainly does work, but logically you're still "splitting" the arrays - you just don't need any work from the computer to do so :-)

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ Personally I really like the bottom up merge sort because it's simpler to implement in a way that lets you avoid allocating a temp buffer at each recursion level. Instead you allocate a buffer once and ping-pong between them. $\endgroup$
    – ratchet freak
    Commented Aug 11, 2017 at 15:55
  • $\begingroup$ This - divide is computationally a no-op... plus OPs suggestion is just an introduction of an equivalent to a merger of single element arrays, and starting using merge from 2nd step, which seems redundant, because original merge works just as well. There is no point in optimizing that. It only introduces redundant concepts and logic. $\endgroup$
    – luk32
    Commented Aug 11, 2017 at 15:56
  • $\begingroup$ @ratchetfreak: I love it too, but sadly it's not equivalent to top-down (at least the version I know). It'll do the merging differently, basically rounding up to the next power-of-2 array length, which I think might even be a bit slower. Do you know of a bottom-up version that does the exact same merges without paying a hefty cost somewhere else? $\endgroup$
    – user541686
    Commented Aug 11, 2017 at 23:41
  • $\begingroup$ @Mehrdad the only real issue is the little tail that needs to be merged in. In the worst case that means another pass to merge in a single item for arrays of length 1<<n+1. Though I'm sure you can adjust things so a too small tail gets merged in in a lower pass. $\endgroup$
    – ratchet freak
    Commented Aug 11, 2017 at 23:59
  • $\begingroup$ @psmears "you just don't need any work from the computer to do so" - so I'm guessing the performance cost of n calls of some recursive divide function (7 calls in the example diagram) is basically negligible? $\endgroup$
    – Jimmy_Rustle
    Commented Aug 12, 2017 at 7:54
11
$\begingroup$

I guess what you mean is the bottom-up implementation. In the bottom up implementation you start from single cell elements an move upward by merging elements into larger sorted lists/arrays. Just reverse the arrows in your figure above starting from the middle array, i.e., one-element arrays.

Also, you may want to optimize the merge sort by dividing arrays until they reach some constant size, after which you simply sort them using for example insertion sort.

Otherwise, sorting without splitting array is not possible. In fact the gist of the Merge sort is dividing and sorting subarrays, i.e., divide-and-conquer.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.