Merge Sort

Design and Strategy

Merge Sort uses the divide-and-conquer approach. It proceeds as follows:

If the list has at most one item, it’s already sorted, so do nothing.
Otherwise, divide the list into two halves—a first half and a second half.
Sort each half independently, using Merge Sort, of course.
Take the two sorted halves and merge them together by always picking the smaller front item from either half. Once one half is empty, copy the remaining elements of the other list to the end of the array. An auxiliary array is needed for this step.

Before we can give a more formal description of the algorithm we must discuss how to accomplish the merge step. If you are unfamiliar with how this is done, please read the Merge section before continuing.

To sort an array \(A\) of length \(n\), we let \(left=0\) and \(right=n-1\) and proceed as follows. (Note: it treats both \(left\) and \(right\) as inclusive endpoints.)

Base case: When your subarray has zero or one element, it is by definition already sorted, so do nothing.
Split the problem in half: For a subarray that starts at index \(\mathrm{left}\) and ends at index \(\mathrm{right}\), compute \[ \mathrm{mid} \;=\; \left\lfloor \frac{\mathrm{left} + \mathrm{right}}{2} \right\rfloor. \] Now you have two smaller tasks: sort the left half of \(A\) \(\bigl(\mathrm{left}\dots\mathrm{mid}\bigr)\) and sort the right half of \(A\) \(\bigl(\mathrm{mid}+1\dots\mathrm{right}\bigr)\).
Sort each half recursively: Call Merge Sort on the left half and then again on the right half.
Merge the sorted halves: Once both halves are individually sorted, Merge them back into a single sorted array.

Implementation in Java, C++, Python

The implementations are initially called as mergeSort(A,0,n-1). An alternative version for Python is given that takes advantage of some shortcuts, but it is not as efficient as the first version.

public static void mergeSort(int[] A, int left, int right) {
  if (left < right) {
    int mid = left + (right - left) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid + 1, right);
    merge(A, left, mid, right);
  }
}

public static void merge(int[] A, int left, int mid, int right) {
  int n1 = mid - left + 1;
  int n2 = right - mid;
  int[] L = new int[n1];
  int[] R = new int[n2];
  // copy into temporary lists
  for (int i = 0; i < n1; i++) 
      L[i] = A[left + i];
  for (int j = 0; j < n2; j++) 
      R[j] = A[mid + 1 + j];
  int i = 0, j = 0, k = left;
  // merge back into A
  while (i < n1 && j < n2) {
    if (L[i] <= R[j]) 
	    A[k++] = L[i++];
    else 
	    A[k++] = R[j++];
  }
  // copy any remaining elements of L (if R is exhausted)
  while (i < n1) 
      A[k++] = L[i++];
  // copy any remaining elements of R (if L is exhausted)
  while (j < n2) 
      A[k++] = R[j++];
}

void mergeSort(int A[], int left, int right) {
  if (left < right) {
    int mid = left + (right - left) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid + 1, right);
    merge(A, left, mid, right);
  }
}

void merge(int A[], int left, int mid, int right) {
  int n1 = mid - left + 1;
  int n2 = right - mid;
  int* L = new int[n1];
  int* R = new int[n2];
  // copy into temporary lists
  for (int i = 0; i < n1; i++) 
      L[i] = A[left + i];
  for (int j = 0; j < n2; j++) 
      R[j] = A[mid + 1 + j];
  int i = 0, j = 0, k = left;
  // merge back into A
  while (i < n1 && j < n2) {
    if (L[i] <= R[j]) 
	    A[k++] = L[i++];
    else 
	    A[k++] = R[j++];
  }
  // copy any remaining elements of L (if R is exhausted)
  while (i < n1) 
      A[k++] = L[i++];
  // copy any remaining elements of R (if L is exhausted)
  while (j < n2) 
      A[k++] = R[j++];
  // delete dynamically allocated memory
  delete[] L;
  delete[] R;
}

def merge_sort(A, left, right):
    if left < right:
        mid = left + (right - left) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid + 1, right)
        merge(A, left, mid, right)

def merge(A, left, mid, right):
    n1 = mid - left + 1
    n2 = right - mid

    # copy into temporary lists
    L = [A[left + i] for i in range(n1)]
    R = [A[mid + 1 + j] for j in range(n2)]

    i = j = 0       # current indices in L and R
    k = left        # current index in A where we write

    # merge back into A
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1

    # copy any remaining elements of L (if R is exhausted)
    while i < n1:
        A[k] = L[i]
        i += 1
        k += 1

    # copy any remaining elements of R (if L is exhausted)
    while j < n2:
        A[k] = R[j]
        j += 1
        k += 1

def merge_sort(A):
    if len(A) <= 1:
        return A
    mid = len(A) // 2
    left = merge_sort(A[:mid])
    right = merge_sort(A[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Time/Space Analysis

Time Complexity: Let \(T(n)\) be the time (number of basic operations) required by Merge Sort to sort an array of length n. We can break each call into three parts:

Divide: Compute the midpoint and split the array into two halves of size roughly \(n/2\). This takes constant time, say \(\alpha\).
Conquer (recursive calls): Recursively call Merge Sort on each half. Each half has size \(\lfloor n/2\rfloor\) or \(\lceil n/2\rceil\), but for simplicity we write it as two calls of size \(n/2\). Since \(T(n)\) is the time to sort an array of size \(n\), it takes \(T(n/2)\) time to sort an array of size \(n/2\). Thus, the two recursive calls take \(2\,T(n/2)\) time.
Combine (merge): Merge the two sorted halves back together with a single left-to-right sweep, comparing elements and copying them into a result. This takes \(\beta\,n\) time (for some constant \(\beta\)).

Since sorting an array of size 1 takes constant time, we get

\[ T(n) \;=\; 2\,T\!\bigl(\tfrac n2\bigr)\;+\;\alpha\;+\;\beta\,n, \quad T(1) = 1. \]

Assuming we only want a bound on the complexity, we can simplify this to

\[ T(n) \;=\; 2\,T\!\bigl(\tfrac n2\bigr)\;+\;n, \quad T(1) = 1. \]

There are various ways of solving this recurrence relation (backward substitution, forward substitution, Master Theorem) that all give us \[T(n)=\Theta(n\log n).\]

Notice that the complexity does not depend on the initial order of elements. Thus, Merge Sort takes a predictable amount of time to sort any array of a given size.

Space Complexity: Merge Sort requires two types of extra space:

Auxiliary arrays: At each merge step, temporary storage of total size \(n\) is allocated to hold the two halves before copying back, for \(\Theta(n)\) extra space.
Recursion stack: The recursion depth reaches \(\lceil \log_{2} n\rceil\), consuming \(\Theta(\log n)\) stack frames, each of constant size.

Thus, overall the space complexity is \(\Theta(\log n\;+\;n)\;=\;\Theta(n)\).

Variations/Improvements

There are several well-known variations and optimizations:

Bottom-Up (Iterative) Merge Sort: Instead of recursing, you start by merging subarrays of size 1, then size 2, 4, 8, and so on, doubling the run size each pass. This eliminates the recursion overhead.
Natural Merge Sort: Leverages existing runs in the input: scan the array to identify already sorted runs (monotonic sequences), then repeatedly merge adjacent runs. On partially ordered data, this can be faster than the Θ(n log n) bound.
In-Place Merge: The typical merge uses Θ(n) auxiliary space. In-place merge algorithms exist—using techniques like block rearrangement or pointer arithmetic—to perform the merge with only Θ(1) extra space, at the cost of more complex code and slightly higher constant factors.
Hybrid Approaches: For small subarrays (e.g. length ≤ 32), switching to an Insertion Sort or selection sort can reduce overhead. This “cut-off” optimization exploits the fact that simple sorts outperform Merge Sort on tiny segments.
Multi-Way Merge: Instead of dividing into two halves, you can split into k > 2 runs and do a k-way merge using a min-heap. This is especially useful in external sorting (e.g. merging many sorted files) to reduce the number of merge passes.
Timsort: A hybrid stable sort combining natural Merge Sort and Insertion Sort: it identifies existing monotonic runs, uses Insertion Sort to extend short runs to a minimum “minrun” length, then merges runs via a stack-based policy with “galloping” when one run consistently outpaces the other. This yields Θ(n) performance on nearly-sorted data and Θ(n log n) worst-case, and is used as the default sort in Python and Java.

Merge Sort

Problem Solved

Design and Strategy

Implementation in Java, C++, Python

Time/Space Analysis

Variations/Improvements

Links to Resources

Reading Comprehension Questions

In-Class Activities

Problems