# Is this a potentially more intuitive approach to MergeSort?

I have read at least one other post (perhaps not on this stackexchange) that asks essentially: Why do we have to break up the array into successively smaller arrays until we finally reach the bottom (of a tree) at which point the merge process begins?

It was instead suggested that we already know the value of nodes on the bottom row: They are simply the elements of input (unsorted) array. We can then sort this array by successively merging nodes, filling in the empty nodes until we reach the top.

I do not know if this is a novel or interesting approach. I can say it seems simpler and is easier to understand for me.

My question: Is this a valid approach, and is it more clear than top-down recursion?

Here is code that seems to work:

package test;

import java.util.Arrays;

class MergeNode {
int[] array;
MergeNode left;
MergeNode right;

MergeNode(int[] arr) {
this.array = arr;
}
}

public class ReverseTreeMergeSort {
MergeNode createTree(int[] arr) {
int n = arr.length;
MergeNode[] nodes = new MergeNode[2 * n - 1];
for (int i = 0; i < n; i++) {
nodes[i + n - 1] = new MergeNode(new int[]{arr[i]});
}
for (int i = n - 2; i >= 0; i--) {
nodes[i] = new MergeNode(new int[0]);
nodes[i].left = nodes[2 * i + 1];
nodes[i].right = nodes[2 * i + 2];
nodes[i].array = merge(nodes[i].left.array, nodes[i].right.array);
}
return nodes[0];
}

int[] merge(int[] arr1, int[] arr2) {
int[] merged = new int[arr1.length + arr2.length];
int i = 0, j = 0, k = 0;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] <= arr2[j]) {
merged[k++] = arr1[i++];
} else {
merged[k++] = arr2[j++];
}
}
while (i < arr1.length) {
merged[k++] = arr1[i++];
}
while (j < arr2.length) {
merged[k++] = arr2[j++];
}
return merged;
}

public static void main(String[] args) {
int[] arr = {88, 77, 3, 2, 1};
ReverseTreeMergeSort sorter = new ReverseTreeMergeSort();
MergeNode root = sorter.createTree(arr);
System.out.println(Arrays.toString(root.array));
}
}

• You can look at recursive problems top-down or bottom-up. Usually top-down is easier for me to reason about.
– qwr
Commented Jul 12 at 4:14
• @qwr the main point for me is that the tree structure and the bottom nodes can be simply derived -- that entire process of splitting the list into smaller lists seem superfluous. Commented Jul 12 at 4:51
• I mean, do you care about efficiency? Your implementation forces every allocated array to exist all at the same time, when a better written merge sort uses logarithmic times less memory.
– Yakk
Commented Jul 12 at 14:41
• @Yakk I did not assert it was efficient, but as I mentioned previously, it helped me understand what was going on: small sorted arrays merged into successively larger sorted arrays. Commented Jul 12 at 16:55
• I think comprehensibility is a matter of taste and experience. I find iterative code like this hard to read when compared to more functional / recursive code, but grasping recursion is a known hurdle in programming education. Once you're comfortable with a certain programming style, it will come across as more legible, but that doesn't make it absolutely true. Commented Jul 13 at 11:59

Usually the more intuitive approach to an algorithm is one you can physically emulate. Cutting a deck into 2 (roughly) equally sized decks is very simple. So the educational variant of merge sort does the same, split the input array into 2 separate arrays.

Doing the sort without allocating extra arrays is then an implementation detail.

Moreover with a proper bottom up you don't need recursion or some tree structure to traverse to pick the merge targets:

for(int i = 1; i < arr.length; i *= 2){
for(int j = 0; j+i < arr.length; j += 2*i){
merge(arr, j, j+i, min(arr.length, j + 2*i));
}
}


where merge(array, start, mid, end) will do a in-place merge of the sub arrays $$[start, mid)$$ and $$[mid, end)$$.

However this algorithm is much less straightforward to verify intuitively. (I'll leave that as an exercise for the reader)

• Is that all the code? or is replacing something in my post? Commented Jul 11 at 15:44
• That's all the code to do a merge sort, and that question handily illustrates how obscure the core algorithm became. Commented Jul 12 at 7:03
• what is merge's definition? are you showing us the merge function which is called recursively? Commented Jul 12 at 7:50
• there is no recursion here, merge is a function that will take 2 adjoining subarrays in the given array and perform a merge on them. The nested loop will call merge repeatedly such that the array becomes sorted. Commented Jul 12 at 8:04
• you mean just the merge of two sorted arrays, right? Commented Jul 12 at 8:06

There are both top-down and bottom-up variants of merge sort. For example, Wikipedia lists implementations for both variants.

One key reason for preferring the top-down variant in an algorithms class is that it is a standard example of a recursive function and it has a simple correctness proof by induction on recursion depth: the recursive calls produce sorted arrays by induction hypothesis, merge combines two sorted arrays into a sorted array, which is the result of merge sort, QED.

In contrast, a bottom-up merge sort deals with arrays of arrays, the proof of correctness is messier, and from an educational standpoint, the high-level lessons students should take away from it are less clear.

• The wikipedia article does not create an explicit tree structure afaict -- this may be unneeded even bad for performance, but to illustrate what is happening by creating a tree that can be printed, may this code is useful? Commented Jul 11 at 15:30
• Keep in mind the bias that code that you just wrote will naturally seem intuitive to you. Pedagogically, making your code do one more thing (building a tree for visualization, in addition to sorting) creates one more hurdle that (1) you have to present and explain (2) students have to overcome to understand what is going on, that is one more opportunity for students to become confused. Showing visualizations is good. Showing the code that creates the visualization is most likely a distraction. Commented Jul 11 at 16:09
• If the main feature of your algorithm is that it creates a tree that reflects the structure of the merge operations, that's nothing special because you can also do that in a top-down merge sort. It's just a lot of boilerplate in Java to return an array and a tree at the same time, but it can be done. Commented Jul 11 at 16:15

Your approach replaces the use of the call stack to store intermediate arrays with an explicit queue of arrays, which aids in implementing Mergesort iteratively rather than recursively. Instead of (using Python-esque pseudocode)

def mergeRecursive(input):
mid = ...
a = mergeRecursive(input[:mid])
b = mergeRecursive(input[mid:])
return merge(a, b)


you have

def mergeIterative(input):
subarrays = [[x] for x in input]
while len(subarrays) > 1:
a = subarray.pop()
b = subarray.pop()
r = merge(a, b)
subarrays.append(r)
return subarrays[0]