Merge Sort: Split, Sort, Merge

Divide and conquer

Merge sort uses recursion (Module 6):

1. Split the array into two halves.
2. Sort each half – by calling merge sort on it.
3. Merge the two sorted halves into one sorted array.

Base case: an array of 0 or 1 items is already sorted.

Think of it like this: Sorting exam papers with a friend: split the pile in two, each sorts their half, then you merge by always taking the smaller top paper from the two piles.

import java.util.Arrays;

public class Main {
    static void mergeSort(int[] a, int lo, int hi) {      // sorts a[lo..hi]
        if (lo >= hi) return;                              // 0 or 1 item
        int mid = (lo + hi) / 2;
        mergeSort(a, lo, mid);
        mergeSort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    static void merge(int[] a, int lo, int mid, int hi) {
        int[] tmp = new int[hi - lo + 1];
        int i = lo, j = mid + 1, k = 0;
        while (i <= mid && j <= hi) {
            if (a[i] <= a[j]) tmp[k++] = a[i++];       // take the smaller front item
            else tmp[k++] = a[j++];
        }
        while (i <= mid) tmp[k++] = a[i++];            // leftovers
        while (j <= hi) tmp[k++] = a[j++];
        for (k = 0; k < tmp.length; k++) a[lo + k] = tmp[k];
        System.out.println("merged " + Arrays.toString(tmp));
    }

    public static void main(String[] args) {
        int[] a = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}

Output

merged [27, 38]
merged [3, 43]
merged [3, 27, 38, 43]
merged [9, 82]
merged [9, 10, 82]
merged [3, 9, 10, 27, 38, 43, 82]
[3, 9, 10, 27, 38, 43, 82]

Why O(n log n)?

Halving 7 items gives about 3 levels of splitting (log n), and on each level merging touches every item once (n). So the total is n × log n. For a million items that's about 20 million steps instead of a trillion for O(n²).

Remember: Merge sort is always O(n log n) and stable (equal items keep their order), but it needs an extra array: O(n) memory.