In merge sort, why not just split to individual items immediately rather than recursively splitting in half?

Question

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);
};

Answer 1

Any recursive function can be converted into an iterative one. Normally, however, you would just use recursion for a Merge Sort, because splitting in half over and over again lends itself naturally to recursion.

To convert a recursive function to an iterative one usually requires an auxiliary stack implementation to replace the stack which recursion gives you for free. However, Merge Sort can be made iterative without such a stack.

Merge Sort, Recursive Version:

void mergeSort(int arr[], int l, int r)
{
   if (l < r)
   {
      int m = l+(r-l)/2; //Same as (l+r)/2 but avoids overflow for large l & h
      mergeSort(arr, l, m);
      mergeSort(arr, m+1, r);
      merge(arr, l, m, r);
   }
}

Merge Sort, Iterative Version:

void mergeSort(int arr[], int n)
{
   int curr_size;  // For current size of subarrays to be merged
                   // curr_size varies from 1 to n/2
   int left_start; // For picking starting index of left subarray
                   // to be merged

   // Merge subarrays in bottom up manner.  First merge subarrays of
   // size 1 to create sorted subarrays of size 2, then merge subarrays
   // of size 2 to create sorted subarrays of size 4, and so on.
   for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size)
   {
       // Pick starting point of different subarrays of current size
       for (left_start=0; left_start<n-1; left_start += 2*curr_size)
       {
           // Find ending point of left subarray. mid+1 is starting 
           // point of right
           int mid = left_start + curr_size - 1;

           int right_end = min(left_start + 2*curr_size - 1, n-1);

           // Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end]
           merge(arr, left_start, mid, right_end);
       }
   }
}

Note that the iterative version requires a nested loop. The merge function is exactly the same in both cases.

Further Reading
Iterative Merge Sort

Answer 2

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).

Answer 3

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.}