Merge Sort in Java

Suppose a teacher has to put 200 answer sheets in roll-number order. Doing it alone is slow. So she splits the pile in two and hands each half to a helper, who splits theirs again, and so on, until each person holds just one sheet, which is already "sorted". Then pairs of helpers combine their sheets into one sorted pile, those piles are combined again, and the final two piles come back to the teacher to be combined once more. That is merge sort: split until the pieces are trivial, then merge sorted pieces back together. In this lesson, you will learn how merge sort works, write it in Java with a trace, and see why it always takes O(n log n) time.

What Is Merge Sort?

Merge sort in Java is a divide and conquer sorting algorithm that is used to sort an array by splitting it into two halves, sorting each half recursively, and merging the two sorted halves into one sorted array.

• It is O(n log n) in every case: best, average and worst.
• It is stable: equal elements keep their order.
• It needs O(n) extra memory for merging.
• Java's Arrays.sort for objects and List.sort use TimSort, an improved merge sort.

How It Works

1. Divide: if the array has 0 or 1 elements, it is already sorted. Otherwise, split it at the middle.
2. Conquer: merge sort the left half and the right half (recursively).
3. Combine: merge the two sorted halves by repeatedly taking the smaller front element of the two.

The Merge Step

Merging is the heart of the algorithm. Given two sorted halves, compare their front elements, copy the smaller one into the result, and move forward in that half. When one half runs out, copy the rest of the other.

Each element is copied once, so merging n elements takes O(n) time.

Merge Sort in Java

Let's see an example that sorts the array from the picture and prints every merge.

import java.util.Arrays;
 
public class MergeSort {
    static void mergeSort(int[] a, int left, int right) {
        if (left >= right) {
            return;                                 // 0 or 1 element
        }
        int mid = left + (right - left) / 2;
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, mid, right);
    }
 
    static void merge(int[] a, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            temp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
        }
        while (i <= mid) {
            temp[k++] = a[i++];
        }
        while (j <= right) {
            temp[k++] = a[j++];
        }
        System.arraycopy(temp, 0, a, left, temp.length);
        System.out.println("merged " + Arrays.toString(temp));
    }
 
    public static void main(String[] args) {
        int[] marks = {38, 27, 43, 3, 9, 82, 10, 19};
        mergeSort(marks, 0, marks.length - 1);
        System.out.println("sorted " + Arrays.toString(marks));
    }
}

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

Explanation:

1. mergeSort keeps splitting at mid until a range holds one element, which is the base case.
2. The merges happen on the way back up the recursion: first pairs, then groups of four, then all eight, matching the bottom half of the picture.
3. merge copies the smaller front element into temp each time, then copies any leftovers, and finally writes temp back into the array.
4. a[i] <= a[j] (not <) takes from the left half when elements are equal. That is what makes merge sort stable.

Counting the Work

• Splitting an array of n elements in half again and again gives about log₂ n levels. For 8 elements, that is 3 levels of merging.
• At each level, every element is merged exactly once, which is O(n) work per level.
• Total: n × log n.

Unlike quick sort, merge sort always splits exactly in half, so there is no bad case: sorted, reversed and random input all take O(n log n).

Merge Sort in the JDK

Arrays.sort(Object[]), Collections.sort and List.sort use TimSort, a merge sort designed by Tim Peters. It finds runs that are already sorted, uses insertion sort for small pieces, and merges runs cleverly, so it is O(n) on sorted data and O(n log n) in the worst case. It is stable, which is why sorting students by name and then by marks keeps students with equal marks in name order.

Interview Corner

Practice

1. Easy: Add a parameter for depth to mergeSort and print the range being split, indented by depth, to see the split tree.
2. Harder: Change merge to sort an array of String names alphabetically using compareTo. Then sort {"Srihitha", "Navika", "Advitha", "Navika"}.

Key Takeaways