Merge Sort: Implementation and Analysis

Merge Sort
Merge sort is a divide and conquer algorithm that sorts objects in O(n log n) time. Merge sort begins by dividing the input list into two sublists, and then continues to divide each subsequent sublist until we are left with a bunch of sublists that each contain one element. Each one element list is considered sorted. Next, Merge sort conquers each sorted sublist by repeatedly merging adjacent sorted sublists This creates bigger and bigger sorted sublists. Once all sublists are merged, the result is the final sorted list.

The following animation from wikimediacommons helps to visualize Merge sort:

Merge sort: The Implementation (Java):

[code language=”Java”]public static class MergeSort {
private char[] chars;
private char[] auxChars;

public void sort(char[] chars) {
this.chars = chars;
auxChars = new char[chars.length];

mergeSort(0, chars.length);

System.out.println(chars);
}

private void mergeSort(int low, int high) {
if (low < high-1) {
int middle = low + (high – low) / 2;
mergeSort(low, middle);
mergeSort(middle, high);
merge(low, middle, high);
}
}

private void merge(int low, int middle, int high) {
for (int i=low; i < high; i++) {
auxChars[i] = chars[i];
}

int s=low, l=low, h=middle;
while (l < middle && h < high) {
if (auxChars[l] > auxChars[h]) {
chars[s++] = auxChars[l++];
} else {
chars[s++] = auxChars[h++];
}
}

// add left overs
while(l < middle) {
chars[s++] = auxChars[l++];
}
while(h < high) {
chars[s++] = auxChars[h++];
}
}
}
[/code]

Merge sort: The Analysis
Let’s assume we are given a list of 8 integers: 15832746

First, Merge sort enters the divide phase. Each call to merge sort halves the list until we have n, 1 item sublists. Since n is a power of 2, e.g. 2^k, we have k = log2 n levels or O(log2 n)

level 0: 1583 2746
level 1: 15 83 27 46
level 2: 1 5 8 3 2 7 4 6

As we can see above, given n = 8 items, we have log2 n = k levels e.g. log2 8 = 3

Secondly, at each level of the recursion, Merge sort performs a merge.

A merge at level 0, calls merge once. Merge merges 2 lists A[low,mid] and B[mid+1,high] requires at most n - 1 comparisons. Merge sort also requires that n items are moved temporarily to an auxiliary list and and then back to the given list. Thus each merge requires 2n + n - 1 = 3n-1 operations.

A merge at level 1 calls merge twice. Each merge, merges 2 lists. In this case, we have n/2 items in each merge, resulting in 3*(n/2) -1 operations. Since we do two merges we have 2 * 3*(n/2) -1 operations or 3n-2 operations.

A merge at level k, calls merge 2^k times. In this case, we have (2^k) * 3*(n/2^k) -1 = 3n - 2^k or O(n). Therefore we know to merge at any level k, we have O(n) operations.

We can visualize it here (note that same colored lists are merged together):

level 2: 1 5 8 3 2 7 4 6
level 1: 51 83 72 64
level 0: 8531 7642

Result: 8764321

Now, let’s we combine the divide phase with the conquer phase. Above, we found that there are O(log2 n)< levels of recursion. Also, at each level of recursion Merge sort performs O(n) operations. Therefore the resulting time complexity for Merge sort is O(n log2 n)

Thank you!