Sorting Basics

Comparison sorting and the n log n wall

Most sorts are comparison sorts: the only question they ever ask the data is, is this element smaller than that one? Bubble sort, insertion sort, merge sort, and quicksort all live under this rule. And the rule imposes a hard limit: no comparison sort can beat O(n log n) comparisons in the worst case, roughly n times the logarithm of n, so about 17n comparisons for a hundred thousand items.

Here is the intuition. There are n! (n factorial) possible orderings of n items (a staggering number) and a correct sort must be able to distinguish every one of them, because any ordering could be the input. Each yes-or-no comparison can at best cut the remaining possibilities in half. Halving your way down from n! possibilities takes log of n! steps, and mathematically that is about n log n. It is the twenty-questions game: with binary questions, distinguishing more possibilities simply requires more questions. No cleverness escapes it, as long as comparisons are all you use.

Merge sort vs. quicksort

The two headline O(n log n) sorts take opposite approaches to divide and conquer. Merge sort splits the array in half, recursively sorts each half, then merges the two sorted halves by repeatedly taking the smaller front element. All the real work happens in the merge, on the way back up. Its virtues: guaranteed O(n log n) in every case, and it is stable, meaning elements that compare equal keep their original relative order. Its cost: it needs O(n) extra memory for the merging.

Quicksort instead picks a pivot element and partitions the array in place: everything smaller than the pivot goes left, everything larger goes right, then each side is sorted recursively. The work happens on the way down, and no merge is needed. It runs O(n log n) on average with excellent constants and almost no extra memory, but consistently terrible pivots degrade it to O(n squared). Rare with randomized pivots, but real. The practical summary: quicksort is usually fastest, merge sort is predictable and stable, and real libraries blend these ideas rather than picking one purely.

void mergeSort(int[] a, int lo, int hi) {
    if (hi - lo <= 1) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid, hi);
    merge(a, lo, mid, hi); // combine two sorted halves
}

Counting sort: cheating the wall, legally

The n log n bound only binds sorts that rely on comparisons. If you know something extra about the data (specifically, that values are integers in a small range) you can skip comparing entirely and sort in O(n + k) time, where k is the size of the value range.

Counting sort works like tallying votes. Make an array of k counters. Sweep the input once, incrementing the counter for each value you see. Then sweep the counters in order, writing out each value as many times as it was counted. No element is ever compared to another; the counter array's own indices provide the order for free. Sorting a million exam scores between 0 and 100 takes one pass plus 101 counters. Dramatically faster than any comparison sort. The catch is the k: sorting arbitrary ints with counting sort would need billions of counters, so it only wins when the range is genuinely small.

int[] countingSort(int[] a, int maxValue) {
    int[] count = new int[maxValue + 1];
    for (int x : a) count[x]++;
    int[] result = new int[a.length];
    int idx = 0;
    for (int v = 0; v <= maxValue; v++) {
        for (int c = 0; c < count[v]; c++) {
            result[idx++] = v;
        }
    }
    return result;
}

What to actually write in Java

In interviews and in production, you almost never hand-roll a sort. You call the library and spend your thinking elsewhere. Arrays.sort(int[]) uses dual-pivot quicksort, an engineered variant that is extremely fast in practice. Arrays.sort on object arrays, and Collections.sort on lists, use Timsort, a merge sort hybrid that is stable and exploits already-sorted runs in the data. Both are O(n log n); the choice of algorithm under the hood is exactly the merge-versus-quick trade-off from earlier, decided for you.

Two idioms to have at your fingertips: sorting with a custom rule via a comparator, and sorting a 2D array of intervals by start point, which opens a whole family of interval problems. And one habit worth forming now: whenever a problem gives you unsorted data and its answer depends on order or proximity, ask what sorting first would buy you. Very often it buys you the next lesson's superpower, because once data is sorted, binary search can find anything in O(log n).

int[] nums = {5, 2, 9, 1};
Arrays.sort(nums); // [1, 2, 5, 9]

Integer[] boxed = {5, 2, 9, 1};
Arrays.sort(boxed, (a, b) -> b - a); // [9, 5, 2, 1]

int[][] intervals = {{3, 4}, {1, 2}, {2, 5}};
Arrays.sort(intervals, (x, y) -> x[0] - y[0]);

Frequently asked