Skip to main content

In merge sort, why not just split to individual items immediately rather than recursively splitting [Resolved]

In learning the merge sort, the examples show the list of items being split in half over and over again and then merged again.

Why not just start with iterating over the individual item pairs in the list sequentially if the initial split action always splits the list into single individual items?

I understand that it is an iterative method vs recursive, but in this particular example it seems like the "divide" step will always seem break it up into single items so I'm a bit unclear about why we would even recursively divide when we can just divite it into single items in one step.

description of merge sort:

The mergeSort function should recursively sort the subarray array[p..r] i.e. after calling mergeSort(array,p,r) the elements from index p to index r of array should be sorted in ascending order.

-If the subarray has size 0 or 1, then it's already sorted, and so nothing needs to be done. -Otherwise, merge sort uses divide-and-conquer to sort the subarray.

Use merge(array, p, q, r) to merge sorted sub arrays array[p..q] and array[q+1..r].

js example

var mergeSort = function(array, p, r) {
    if (r === p)
        return array;

    var q = p + floor((r - p)/2);

    mergeSort(array, p, q);
    mergeSort(array, q+1, r);
    merge(array, p, q, r);

Question Credit: MonkeyBonkey
Question Reference
Asked March 16, 2018
Posted Under: Programming
3 Answers

Because the whole point is to minimize the number of merge steps.

I'm not really sure what you imagine this "start with iterating over the individual item pairs in the list sequentially" would actually do. I'll assume you mean to take the first pair, trivially sort it, then merge it with the second sorted pair, then merge the result with the third pair. In that case you'll have to perform n/2 merge steps, which will on average involve iterating over n/2 items... so O(n^2). But with the "real" merge sort, you have only log2(n) merge steps, for a total complexity of O(log(n)*n).

credit: Michael Borgwardt
Answered March 16, 2018

Because you need the tree structure to traverse. (And the call stack traverses it for you.)

If you build the tree from the bottom up, as you're essentially suggesting, you're not performing any less work; you're just tracking the intermediate results differently -- and making the algorithm more complicated and less intuitive in my opinion.

As Robert Harvey's answer implies (but doesn't directly state), building from the bottom up is a more iterative approach. But, an iterative approach still needs to create all the same containers and trackers as the call-stack/tree would for the intermediate return values.

The difference is that you have more work to do in the iterative solution.

What might be worth noting: If you start dealing with arrays that don't fit in memory, it might actually be advantageous to do as you say and build, much more manually, from the bottom up — which could allow you to work more intelligently off a disk.

credit: svidgen
Answered March 16, 2018
Your Answer