Merge sort

Divide: split arr[lo..hi] at mid. Conquer: sort both halves recursively. Combine: merge the two sorted halves. A single element is already sorted, which is the base case.

The recursion tree has about log₂ n levels, and the merges on each level touch every element once. That gives n work per level and O(n log n) in total, regardless of the input order. Step through the animation and watch the call stack, the tmp[] buffer and the sorted runs grow.

1public static void mergeSort(int[] arr, int lo, int hi) {
2    if (hi - lo < 1) return;
3    int mid = lo + (hi - lo) / 2;
4    mergeSort(arr, lo, mid);
5    mergeSort(arr, mid + 1, hi);
6    merge(arr, lo, mid, hi);
7}
8
9static void merge(int[] arr, int lo, int mid, int hi) {
10    int[] tmp = new int[hi - lo + 1];
11    int i = lo, j = mid + 1, k = 0;
12    while (i <= mid && j <= hi) {
13        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
14        else tmp[k++] = arr[j++];
15    }
16    while (i <= mid) tmp[k++] = arr[i++];
17    while (j <= hi) tmp[k++] = arr[j++];
18    System.arraycopy(tmp, 0, arr, lo, tmp.length);
19}

Merging keeps one pointer at the head of each sorted run, i and j. Compare the two heads, copy the smaller into tmp, and advance that pointer. When one run runs out, copy the remainder of the other, since it is already sorted.

Merging two runs of sizes a and b takes at most a + b - 1 comparisons and exactly a + b writes. That linear cost is what makes the whole algorithm O(n log n).

For n = 8 the worst case is n⌈log₂ n⌉ - 2^⌈log₂ n⌉ + 1 = 17 comparisons. The default animation input reaches exactly that.

Merge sort is stable if, on ties, the element from the left run is taken first. That is the <= in arr[i] <= arr[j]. Elements from the left run came earlier in the input, so equal keys keep their original order.

Writing < there still sorts correctly but silently destroys stability. Run the “Duplicates” preset and check that the a/b tags stay in order.

Allocating a new tmp array inside every merge creates O(n) garbage per level. Allocate one buffer of size n up front and reuse it in every merge call. Space stays O(n), plus O(log n) recursion stack.

Two further optimisations are worth knowing. If arr[mid] <= arr[mid + 1] the halves are already in order, so skip the merge (this makes already sorted input O(n)). And for small ranges, insertion sort is faster than recursing.

1public static void mergeSort(int[] arr) {
2    int[] buffer = new int[arr.length];          // allocated once, reused by every merge
3    sort(arr, buffer, 0, arr.length - 1);
4}
5
6private static void sort(int[] arr, int[] buf, int lo, int hi) {
7    if (lo >= hi) return;
8    int mid = lo + (hi - lo) / 2;
9    sort(arr, buf, lo, mid);
10    sort(arr, buf, mid + 1, hi);
11    if (arr[mid] <= arr[mid + 1]) return;        // already in order: skip the merge
12    merge(arr, buf, lo, mid, hi);
13}
14
15private static void merge(int[] arr, int[] buf, int lo, int mid, int hi) {
16    System.arraycopy(arr, lo, buf, lo, hi - lo + 1);
17    int i = lo, j = mid + 1;
18    for (int k = lo; k <= hi; k++) {
19        if (i > mid)              arr[k] = buf[j++];
20        else if (j > hi)          arr[k] = buf[i++];
21        else if (buf[j] < buf[i]) arr[k] = buf[j++];   // strict <: ties take the left element
22        else                      arr[k] = buf[i++];
23    }
24}

Bottom-up merge sort removes the recursion. Treat the array as n runs of width 1, merge neighbouring pairs into runs of width 2, then 4, then 8, and so on until one run remains.

It performs the same merges as the top-down version when n is a power of two, uses no call stack, and is a natural fit for sorting data that arrives in runs. The last run of a round may be shorter, so clamp hi to n - 1.

1public static void mergeSortBottomUp(int[] arr) {
2    int n = arr.length;
3    for (int width = 1; width < n; width *= 2) {
4        for (int lo = 0; lo < n - width; lo += 2 * width) {
5            int mid = lo + width - 1;
6            int hi = Math.min(lo + 2 * width - 1, n - 1);
7            merge(arr, lo, mid, hi);
8        }
9    }
10}
11
12static void merge(int[] arr, int lo, int mid, int hi) {
13    int[] tmp = new int[hi - lo + 1];
14    int i = lo, j = mid + 1, k = 0;
15    while (i <= mid && j <= hi) {
16        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
17        else tmp[k++] = arr[j++];
18    }
19    while (i <= mid) tmp[k++] = arr[i++];
20    while (j <= hi) tmp[k++] = arr[j++];
21    System.arraycopy(tmp, 0, arr, lo, tmp.length);
22}

Merge sort is the standard way to sort a linked list. Arrays make splitting free but merging needs a buffer; lists are the opposite: finding the middle costs O(n) (slow and fast pointers), but merging just relinks nodes, so no extra buffer is needed.

Quick sort and heap sort depend on random access, which lists do not have, so merge sort wins here. Extra space is only the O(log n) recursion stack.

1static ListNode sortList(ListNode head) {
2    if (head == null || head.next == null) return head;
3    ListNode slow = head, fast = head.next;            // find the middle
4    while (fast != null && fast.next != null) {
5        slow = slow.next;
6        fast = fast.next.next;
7    }
8    ListNode right = slow.next;
9    slow.next = null;                                   // cut the list in two
10    return merge(sortList(head), sortList(right));
11}
12
13static ListNode merge(ListNode a, ListNode b) {
14    ListNode dummy = new ListNode(0), tail = dummy;
15    while (a != null && b != null) {
16        if (b.val < a.val) { tail.next = b; b = b.next; }   // ties keep the left node
17        else               { tail.next = a; a = a.next; }
18        tail = tail.next;
19    }
20    tail.next = (a != null) ? a : b;
21    return dummy.next;
22}