Merge Sort

The Merge Process

We want to combine two lists so that the resulting merged list remains sorted.

We basically copy and sort at the exact same time.

1. Supposed we have sorted arrays A and B and pointers i and j point to the first element of A and B respectively.

2. Create array C with enough space.

3. Populate the elements of C one-by-one C[k] = min(A[i], B[k]) increment i/j If i reaches the end of A, then add the rest of B.

   Combining is linear time.

Code:

private static void merge(int[] arr, int left, int mid, int right) {  
  int i = left; // pointer for array A  
  int j = mid; //  pointer for array B  
  int k = 0; // pointer for array C  
  int[] c = new int[right - left];  
  
  // while both A and B are still valid copy the greater value to C  
  while (i < mid && j < right) {  
    c[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];  
  }  
  
  // copy leftover values from A to C  
  while (i < mid) {  
    c[k++] = arr[i++];  
  }  
  // copy leftover values from B to C  
  while (j < right) {  
    c[k++] = arr[j++];  
  }  
  
  // everything is copied and sorted in C  
  System.arraycopy(c, 0, arr, left, c.length);  
}

Merge Sort: Big Picture

1. divide the sequence into subsequences of singletons (sequence that consists fo one elemenet).
2. successively merge the subsequences pairwise until a single sequence is reformed.

This is called the "divide and conquer" strategy.

• divide up to the small problems, fix that smaller problem, then assemble to solve the bigger problem.
• divide and conquer strategies are typically recursive.
• Their runtimes can be described as T(n) = a * T(n/b) + c

For our code (below), T(n) = 2 * T(n/b) + O(n). This simplifies to T(n) = O(n lg n),

Code:

private static void mergesort(int[] arr, int left, int right) {  
  // singleton is the smallest we want to go to  
  // an array with zero or 1 element is already sorted  
  if ((right - left) <= 1) {  
    return;  
  }  
  int mid = (right + left) / 2;  
  
  mergesort(arr, left, mid);  
  mergesort(arr, mid, right);  
  merge(arr, left, mid, right);  
}

• The number of recursive calls you make is by the power of 2. So the number of rows is lg N and at each row you spend a linear amount of time at each row.
  • Recursive calls are linear.
  • At every level, the amount of work is k * O(n/k). and k goes from 1 to n.
• O(n) + O(n lg n)

A good book to read is Turing's Cathedral: The Origins of the Digital Universe. (technical but still related to CS)

Optimization

In bubble sort, we could optimize it by stopping early when the input has been detected to already be sorted. It allows bubble sort to run in O(n).

The merge sort algorithm can also be optimized to run in O(n) when the input sequence is already sorted.

• If we got a subsequence that is already sorted, then we can save ourselves the linear time of doing the sort on the subsequence and skip directly to the merging.
• How do we recognize this case in constant time?

Answer: Since the (in-place) merge operation assumes the two sub-arrays (to be merged) are already sorted, we can check if the last element of the first subarray is less than or equal to the first element of the second sub-array. In that case we can escape merging:

if (a[mid - 1] > a[mid]) { // escape comparision      
	merge(a, left, mid, right) 
}

The runtime will be O(n)O(n) because the "escape comparison" is done for every pair of subarrays level by level as you merge nnsubarrays to n/2n/2 to n/4n/4 to …… to 11 array. So the total number of comparisons would be n/2+n/4+n/8+⋯+1n/2+n/4+n/8+⋯+1 which is O(n)O(n)