Idea: Divide array into halves, sort, merge

• Time: O(n log n)
• Space: O(n)
• Stable: ✅

Used in

• Linked lists
• External sorting
• Java streams (for objects)

public class MergeSort {
    public static void sort(int[] a) {
        if (a.length < 2) return;
        int[] tmp = new int[a.length];
        sort(a, tmp, 0, a.length - 1);
    }

    private static void sort(int[] a, int[] tmp, int l, int r) {
        if (l >= r) return;
        int m = l + (r - l) / 2;
        sort(a, tmp, l, m);
        sort(a, tmp, m + 1, r);
        merge(a, tmp, l, m, r);
    }

    private static void merge(int[] a, int[] tmp, int l, int m, int r) {
        int i = l, j = m + 1, k = l;
        while (i <= m && j <= r) {
            tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // <= keeps stability
        }
        while (i <= m) tmp[k++] = a[i++];
        while (j <= r) tmp[k++] = a[j++];
        for (int x = l; x <= r; x++) a[x] = tmp[x];
    }
}

Watch for

• Divide → conquer → merge
• Sorted halves merging

Mental model: 🧩 Split, then merge cleanly