DSA 0x202 - Sorting Algorithms

Hmm.., It is going to be a lengthy article. Sorting is an important topic in Data structures and Algorithms.

Why Sorting Matters

It unlocks binary search. Finding a value in an unsorted array of a million elements takes O(n) We need to check every element. Sorted, binary search finds it in about 20 comparisons. So sorting once to search once is a loss. Sorting once to search many times is an enormous win.

Lets say we want to find duplicates. After sorting they are adjacent. What about the median? Index the middle. Find the i-th largest? Just the take the value at the index.

The Terminology

Four properties classify every sorting algorithm, and the comparison table at the end is meaningless without them.

• In-place : uses O(1) extra memory, beyond a few variables. Sorting a 10 GB file matters a lot more when you do not need another 10 GB.

• Stable : elements comparing equal keep their original relative order. This matters more than it sounds; there is a full section on it below.

• Adaptive : runs faster on input that is already partly sorted. Real data is very often partly sorted, so this is worth real money.

• Comparison-based : decides everything by asking "is a before b?" Every algorithm here except counting sort is comparison-based, and that restriction imposes a hard speed limit we will prove.

Swapping function

public static void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
} 

Bubble Sorting Algorithm

Bubble sorting algorithm is the simplest sorting algorithm there is. We walk trough the array, compare adjacent elements, swap them if they are out of order. Repeat until a full pass makes no swaps.

It is called bubble sort because on each pass the largest remaining element "bubbles up" to the end.

Tracing it

Sorting [5, 3, 8, 1, 2]:

block-beta
  columns 5
  a0["5"] a1["3"] a2["8"] a3["1"] a4["2"]
  space:5
  p1("i") --> a0 p2("i + 1") --> a1

block-beta
  columns 5
  a0["3"] a1["5"] a2["8"] a3["1"] a4["2"]
  space:5
  space p1("i") --> a1 p2("i + 1") --> a2

block-beta
  columns 5
  a0["3"] a1["5"] a2["8"] a3["1"] a4["2"]
  space:5
  space:2 p1("i") --> a2 p2("i + 1") --> a3

block-beta
  columns 5
  a0["3"] a1["5"] a2["1"] a3["8"] a4["2"]
  space:5
  space:3 p1("i") --> a3 p2("i + 1") --> a4

block-beta
  columns 5
  a0["3"] a1["5"] a2["1"] a3["2"] a4["8"]
  space:5
  space:4 p1("i") --> a4
  classDef done fill:#008987,stroke:#00605f,color:#ffffff
  class a4 done

The 8 travelled all the way from index 2 to the end, riding along on every swap. It is now in its final position, so pass 2 can ignore it.

block-beta
  columns 5
  c0["3"] c1["1"] c2["2"] c3["5"] c4["8"]
  classDef done fill:#008987,stroke:#00605f,color:#ffffff
  class c3,c4 done

block-beta
  columns 5
  d0["1"] d1["2"] d2["3"] d3["5"] d4["8"]
  classDef done fill:#008987,stroke:#00605f,color:#ffffff
  class d2,d3,d4 done

Why O(n²)

Pass 1 does n-1 comparisons, pass 2 does n-2, and so on. The total is (n-1) + (n-2) + ... + 1 = n(n-1)/2, which is O(n²).

For 10 elements that is 45 comparisons. For 10,000 it is about 50 million.

The early exit

If a full pass makes no swaps, the array is sorted and we can stop.

public static void bubbleSort(int[] arr) {
    int n = arr.length;

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, i, j);
            }
        }
    }
}

public static void bubbleSort(int[] arr) {
    int n = arr.length;

    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, i, j);
                swapped = true;
            }
        }
        if (!swapped) break;          // already sorted, stop
    }
}

The n - 1 - i bound is the second optimisation: after pass i, the last i elements are final, so there is no point looking at them.

With the early exit, an already-sorted array costs one pass, O(n). That makes bubble sort adaptive. It is also stable and in-place. It is still not something you should ship.

Selection Sorting Algorithm

A different strategy: repeatedly select the smallest remaining element and put it where it belongs.

1. Scan the whole array for the minimum. Swap it into position 0.
2. Scan from position 1 onward for the next minimum. Swap it into position 1.
3. Repeat.

It is how you might sort a hand of cards by repeatedly pulling out the lowest one.

Tracing it

Sorting [29, 10, 14, 37, 13]:

block-beta
  columns 5
  a0["29"] a1["10"] a2["14"] a3["37"] a4["13"]

minimum of the whole array is 10 at index 1. Swap with index 0.

block-beta
  columns 5
  b0["10"] b1["29"] b2["14"] b3["37"] b4["13"]
  classDef done fill:#008987,stroke:#00605f,color:#ffffff
  class b0 done

minimum of [29, 14, 37, 13] is 13 at index 4. Swap with index 1.

block-beta
  columns 5
  c0["10"] c1["13"] c2["14"] c3["37"] c4["29"]
  classDef done fill:#008987,stroke:#00605f,color:#ffffff
  class c0,c1 done

minimum of [14, 37, 29] is 14, already at index 2. No swap needed, but the scan still happened.

block-beta
  columns 5
  d0["10"] d1["13"] d2["14"] d3["37"] d4["29"]
  classDef done fill:#008987,stroke:#00605f,color:#ffffff
  class d0,d1,d2 done

minimum of [37, 29] is 29 at index 4. Swap with index 3.

block-beta
  columns 5
  e0["10"] e1["13"] e2["14"] e3["29"] e4["37"]
  classDef done fill:#008987,stroke:#00605f,color:#ffffff
  class e0,e1,e2,e3,e4 done

Why it is always O(n²)

This is the gotcha. Selection sort has no early exit and no adaptivity. To know which element is smallest, it must look at all of them — even if the array is already perfectly sorted. It cannot tell.

pass 1: scan n-1 elements
pass 2: scan n-2 elements
...
total:  n(n-1)/2 comparisons, always

Best case, average case, worst case: all O(n²). Selection sort is the only algorithm here whose best case is no better than its worst.

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) minIndex = j;
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

Its one redeeming quality

Selection sort performs at most n-1 swaps, and that bound is tight regardless of input. On a shuffled 1,000-element array it made 993. Every other O(n²) algorithm here can do O(n²) writes.

If comparisons are cheap but writes are expensive sorting large structs by value, or writing to flash memory where every write wears the cell that property is worth something. It is a narrow niche, but it is a real one.

Note that selection sort is not stable. Swapping a distant minimum into place jumps it over any equal elements in between.

Insertion Sort

The way people actually sort cards in their hand. Take the next card, slide it left past everything bigger, drop it in place.

The array is conceptually split: a sorted prefix on the left, unexamined elements on the right. Each step grows the prefix by one.

Tracing it

Sorting [7, 3, 5, 1, 9]. The prefix starts as just [7], trivially sorted.

block-beta
  columns 5
  a0["7"] a1["3"] a2["5"] a3["1"] a4["9"]
  classDef done fill:#008987,stroke:#00605f,color:#ffffff
  class a0 done

one shift: 7 moves right, 3 lands at index 0.

block-beta
  columns 5
  b0["3"] b1["7"] b2["5"] b3["1"] b4["9"]
  classDef done fill:#008987,stroke:#00605f,color:#ffffff
  class b0,b1 done

one shift: 7 moves right, 5 stops when it meets 3.

block-beta
  columns 5
  c0["3"] c1["5"] c2["7"] c3["1"] c4["9"]
  classDef done fill:#008987,stroke:#00605f,color:#ffffff
  class c0,c1,c2 done

three shifts, all the way to the front. This is the expensive case.

block-beta
  columns 5
  d0["1"] d1["3"] d2["5"] d3["7"] d4["9"]
  classDef done fill:#008987,stroke:#00605f,color:#ffffff
  class d0,d1,d2,d3 done

One comparison against 7 and it stays put.

block-beta
  columns 5
  e0["1"] e1["3"] e2["5"] e3["7"] e4["9"]
  classDef done fill:#008987,stroke:#00605f,color:#ffffff
  class e0,e1,e2,e3,e4 done

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];       // shift right
            j--;
        }
        arr[j + 1] = key;              // drop into the gap
    }
}

Note that it shifts rather than swapping. A swap is three writes; a shift is one. That constant factor is a large part of why insertion sort beats bubble sort in practice despite identical asymptotics.

Why it is the best of the three

Insertion sort is genuinely adaptive, and not just in the already-sorted case. Its cost is proportional to the number of inversions pairs that are out of order relative to each other. Measured on 1,000 elements:

That last figure is exactly n(n-1)/2, the maximum possible every element shifts past every earlier one. But the already-sorted case does no work at all, and the nearly-sorted case does about 1% of the worst case.

Insertion sort is stable, in-place, adaptive, and has very low constant-factor overhead. Those properties are why it is not merely a teaching example: it is a real component inside the sorting routines shipped in Java's standard library, which switch to it for small subarrays.

The three O(n²) sorts, compared

If you only remember one of the three, remember insertion sort.

Merge Sort

Now the algorithms that scale. Merge sort is divide and conquer: split the array in half, sort each half recursively, then merge the two sorted halves.

The insight that makes it work: merging two already-sorted arrays is easy and linear. Look at the front of each, take the smaller, repeat.

The split phase

Sorting [38, 27, 43, 3, 9, 82, 10]. Keep halving until every piece has one element, which is sorted by definition:

graph TD
    A["38 27 43 3 9 82 10"] --- B["38 27 43 3"]
    A --- C["9 82 10"]
    B --- D["38 27"]
    B --- E["43 3"]
    C --- F["9 82"]
    C --- G["10"]
    D --- H["38"]
    D --- I["27"]
    E --- J["43"]
    E --- K["3"]
    F --- L["9"]
    F --- M["82"]

No comparisons happen here. Splitting is pure bookkeeping.

The merge phase

All the work is on the way back up:

graph BT
    H["38"] --- D["27 38"]
    I["27"] --- D
    J["43"] --- E["3 43"]
    K["3"] --- E
    L["9"] --- F["9 82"]
    M["82"] --- F
    G["10"] --- C["9 10 82"]
    F --- C
    D --- B["3 27 38 43"]
    E --- B
    B --- A["3 9 10 27 38 43 82"]
    C --- A
    classDef top fill:#008987,stroke:#00605f,color:#ffffff
    class A top

Here is one merge in detail, combining [27, 38] with [3, 43]:

left [27, 38]   right [3, 43]           result []
cmp 27 >  3   take 3  from right   ->   [3]
cmp 27 <= 43  take 27 from left    ->   [3, 27]
cmp 38 <= 43  take 38 from left    ->   [3, 27, 38]
left is empty, drain 43 from right ->   [3, 27, 38, 43]

And the final merge at the root:

left [3, 27, 38, 43]   right [9, 10, 82]     result []
cmp 3  <= 9    take 3  from left   ->   [3]
cmp 27 >  9    take 9  from right  ->   [3, 9]
cmp 27 >  10   take 10 from right  ->   [3, 9, 10]
cmp 27 <= 82   take 27 from left   ->   [3, 9, 10, 27]
cmp 38 <= 82   take 38 from left   ->   [3, 9, 10, 27, 38]
cmp 43 <= 82   take 43 from left   ->   [3, 9, 10, 27, 38, 43]
left is empty, drain 82 from right ->   [3, 9, 10, 27, 38, 43, 82]

Why O(n log n)

Look at the tree. Halving repeatedly gives log₂(n) levels. At every level, the merges together touch each of the n elements exactly once, so each level costs O(n). Multiply: O(n log n).

That reasoning holds regardless of input. Merge sort has no bad cases best, average, and worst are all O(n log n). For 10,000 elements that is roughly 10,000 × 14 = 140,000 operations, against bubble sort's 50 million.

The cost: O(n) extra space

Merging cannot easily be done in place. The standard implementation copies both halves into temporary arrays first.

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;     // avoids overflow
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1, n2 = right - mid;
    int[] leftArr = new int[n1], rightArr = new int[n2];

    for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];
    for (int i = 0; i < n2; i++) rightArr[i] = arr[mid + 1 + i];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) arr[k++] = leftArr[i++];
        else                           arr[k++] = rightArr[j++];
    }
    while (i < n1) arr[k++] = leftArr[i++];
    while (j < n2) arr[k++] = rightArr[j++];
}

Two details worth pausing on.

left + (right - left) / 2 instead of (left + right) / 2. These are mathematically identical but differ on real hardware: the second overflows when left + right exceeds Integer.MAX_VALUE. This exact bug sat in Java's own binary search implementation for nine years before being found in 2006.

The <= in the comparison. Change it to < and merge sort stops being stable. On a tie it would take from the right array, putting a later element ahead of an earlier equal one. One character.

Merge sort is also the algorithm of choice for linked lists, where it can run with O(1) extra space merging lists just relinks nodes, and the lack of random access that hurts quicksort does not matter here.

Quick Sort

Also divide and conquer, but with the work in the opposite place. Merge sort splits trivially and merges expensively; quick sort partitions expensively and combines trivially.

Pick a pivot. Rearrange so everything smaller sits left of it and everything larger sits right. The pivot is now in its final position forever. Recurse on both sides. There is no combine step when the recursion finishes, the array is sorted.

Partitioning, step by step

The Lomuto scheme, using the last element as pivot. Partitioning [6, 3, 8, 1, 5, 2, 7, 4]:

block-beta
  columns 8
  a0["6"] a1["3"] a2["8"] a3["1"] a4["5"] a5["2"] a6["7"] a7["4"]
  classDef pivot fill:#e67e22,stroke:#b35c0c,color:#ffffff
  class a7 pivot

Pivot is 4. We keep a boundary i marking the end of the "small" zone, and scan with j.

i = -1 (small zone is empty)

j=0  a[j]=6  >  4   leave it            [6, 3, 8, 1, 5, 2, 7, 4]
j=1  a[j]=3 <=  4   i->0, swap i,j      [3, 6, 8, 1, 5, 2, 7, 4]
j=2  a[j]=8  >  4   leave it            [3, 6, 8, 1, 5, 2, 7, 4]
j=3  a[j]=1 <=  4   i->1, swap i,j      [3, 1, 8, 6, 5, 2, 7, 4]
j=4  a[j]=5  >  4   leave it            [3, 1, 8, 6, 5, 2, 7, 4]
j=5  a[j]=2 <=  4   i->2, swap i,j      [3, 1, 2, 6, 5, 8, 7, 4]
j=6  a[j]=7  >  4   leave it            [3, 1, 2, 6, 5, 8, 7, 4]

place pivot: swap index i+1 = 3 with index 7

block-beta
  columns 8
  b0["3"] b1["1"] b2["2"] b3["4"] b4["5"] b5["8"] b6["7"] b7["6"]
  classDef pivot fill:#008987,stroke:#00605f,color:#ffffff
  classDef small fill:#e67e22,stroke:#b35c0c,color:#ffffff
  classDef big fill:#7f8c8d,stroke:#515a5a,color:#ffffff
  class b3 pivot
  class b0,b1,b2 small
  class b4,b5,b6,b7 big

The 4 is now at index 3, which is exactly where it belongs in the finished array, and it will never move again. Everything left of it is smaller, everything right is larger. Recurse into [3, 1, 2] and [5, 8, 7, 6].

Notice neither side is sorted yet partitioning only guarantees which side of the pivot each element is on.

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);       // p itself is already final
    }
}

private static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
        }
    }
    int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
    return i + 1;
}

Pivot choice is everything

Here is quick sort's weakness. If the pivot splits the array roughly in half, you get log(n) levels and O(n log n). If it splits off one element at a time, you get n levels and O(n²).

And the worst case is not some exotic input. It is already-sorted data. With the last element as pivot, the pivot is always the maximum, everything goes into the left partition, and each level removes exactly one element.

Measured recursion depth on 2,000 elements:

log₂(2000) is about 11, so the shuffled case is within a small factor of optimal. The sorted case is catastrophic quadratic time, and deep enough to overflow the stack on a large enough input.

This is a genuine production hazard, because sorted or nearly-sorted input is extremely common. Three standard fixes:

• Random pivot. Pick a random index and swap it to the end before partitioning. No specific input is reliably bad any more; an adversary would have to guess your random seed.
• Median-of-three. Take the median of the first, middle, and last elements. Cheap, and it makes sorted input the best case rather than the worst. This is what most real implementations do.
• Introsort. Track recursion depth, and if it exceeds about 2 log n, bail out to heap sort for that subarray. This is what C++'s std::sort does, giving a genuine O(n log n) worst case while keeping quicksort's speed in the common case.

Quick sort vs merge sort

Merge sort is O(n log n) always; quick sort can degrade to O(n²). So why is quick sort usually faster in practice?

Memory. Quick sort partitions in place. It needs only O(log n) stack space for the recursion, against merge sort's O(n) for temporary arrays.

Cache locality. Partitioning scans linearly through a contiguous block, and the two indices stay near each other. Modern CPUs prefetch this pattern almost perfectly. Merge sort bounces between three separate arrays. The asymptotics do not capture this, but it is often a 2-3× difference in wall-clock time.

Fewer writes on average, and no allocation in the inner loop.

The trade-off in one line: quick sort is faster in the common case, merge sort is stable and never has a bad case.

Heap Sort, Briefly

There is a third O(n log n) algorithm worth knowing: heap sort. Build a max-heap from the array, then repeatedly swap the root (the maximum) to the end and sift down.

It is O(n log n) in the worst case, like merge sort, and in-place, like quick sort seemingly the best of both. In practice it is slower than either, because its access pattern jumps around the array following heap indices and defeats the cache. It is not stable.

Its niche is as a safety net: it is the algorithm introsort falls back to when quicksort goes bad. Heaps get their own post in this series, so I will leave it there.

The n log n Lower Bound

Here is something more interesting than any single algorithm: a proof that no comparison-based sort can beat O(n log n). Not "nobody has found one yet" it cannot exist.

Think of any comparison sort as a decision tree. Each internal node is one comparison, each branch is an outcome, and each leaf is a final ordering. Here is the complete tree for three elements:

graph TD
    N0["cmp a, b"]
    N0 -->|"a first"| N1["cmp b, c"]
    N0 -->|"b first"| N2["cmp a, c"]
    N1 -->|"b first"| R1["a b c"]
    N1 -->|"c first"| N3["cmp a, c"]
    N2 -->|"a first"| R2["b a c"]
    N2 -->|"c first"| N4["cmp b, c"]
    N3 -->|"a first"| R3["a c b"]
    N3 -->|"c first"| R4["c a b"]
    N4 -->|"b first"| R5["b c a"]
    N4 -->|"c first"| R6["c b a"]
    classDef leaf fill:#008987,stroke:#00605f,color:#ffffff
    class R1,R2,R3,R4,R5,R6 leaf

The argument is three steps:

1. Every possible ordering needs its own leaf. With n distinct elements there are n! orderings, so the tree needs at least n! leaves. For n=3 that is 6, and the tree above has exactly 6.
2. A binary tree with L leaves has height at least log₂(L). Each comparison only doubles the reachable leaves.
3. So the height is at least log₂(n!). And by Stirling's approximation, log₂(n!) ≈ n log₂(n) - 1.44n, which is Θ(n log n).

The height of the tree is the number of comparisons in the worst case. So every comparison sort needs Ω(n log n) comparisons on some input. Merge sort and heap sort achieve that bound, which makes them asymptotically optimal.

For n=3 the bound gives log₂(6) = 2.58, rounded up to 3 comparisons exactly the height of the tree above.

Beating the Bound: Counting Sort

The proof has a loophole. It only applies to algorithms whose only tool is comparison. If you can look at the values themselves, the bound does not apply.

Counting sort does exactly that. Count how many times each value appears, then reconstruct the array from the counts.

Sorting [4, 2, 2, 8, 3, 3, 1, 0, 8] where values are known to be in 0..8:

block-beta
  columns 9
  v0["4"] v1["2"] v2["2"] v3["8"] v4["3"] v5["3"] v6["1"] v7["0"] v8["8"]

Count each value:

block-beta
  columns 9
  i0["val 0"] i1["val 1"] i2["val 2"] i3["val 3"] i4["val 4"] i5["val 5"] i6["val 6"] i7["val 7"] i8["val 8"]
  c0["1"] c1["1"] c2["2"] c3["2"] c4["1"] c5["0"] c6["0"] c7["0"] c8["2"]
  classDef hdr fill:#7f8c8d,stroke:#515a5a,color:#ffffff
  classDef cnt fill:#008987,stroke:#00605f,color:#ffffff
  class i0,i1,i2,i3,i4,i5,i6,i7,i8 hdr
  class c0,c1,c2,c3,c4,c5,c6,c7,c8 cnt

Read the counts left to right and write out that many of each value:

block-beta
  columns 9
  o0["0"] o1["1"] o2["2"] o3["2"] o4["3"] o5["3"] o6["4"] o7["8"] o8["8"]
  classDef done fill:#008987,stroke:#00605f,color:#ffffff
  class o0,o1,o2,o3,o4,o5,o6,o7,o8 done

public static int[] countingSort(int[] arr, int maxVal) {
    int[] count = new int[maxVal + 1];
    for (int v : arr) count[v]++;                   // tally

    for (int i = 1; i <= maxVal; i++)
        count[i] += count[i - 1];                   // running totals = end positions

    int[] out = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--)       // backwards, to stay stable
        out[--count[arr[i]]] = arr[i];
    return out;
}

O(n + k) time, where k is the range of values. When k is comparable to n, that is linear genuinely faster than any comparison sort.

The catch is in that k. Sorting a million 32-bit integers this way would need a count array of four billion entries. Counting sort is for small, known integer ranges: exam scores, ages, bytes, priority levels.

Walking the input backwards in the final loop is what makes it stable, and that is not a detail it is what lets radix sort work. Radix sort applies a stable counting sort to one digit at a time, least significant first, sorting n integers of d digits in O(d(n + k)). Its stability is what preserves the ordering established by previous digits.

Stability

An algorithm is stable if elements comparing equal keep their original relative order.

Why care? Because it lets you sort by multiple keys, one at a time. Sort by name, then stably sort by grade, and you get grades in order with names alphabetical within each grade. Without stability the second sort destroys the first.

Here is a real run. Four students, already in name order, sorted by grade:

input:            (2,Alice) (1,Bob) (2,Carol) (1,Dave)

stable (merge):   (1,Bob) (1,Dave) (2,Alice) (2,Carol)
unstable (sel.):  (1,Bob) (1,Dave) (2,Carol) (2,Alice)
                                       ^^^^^^^^^^^^^^
                          Alice and Carol swapped for no reason

Both outputs are correctly sorted by grade. Only the stable one keeps Alice before Carol.

Verified empirically against a test that sorts keyed items and checks each equal-key group stayed in original order:

Selection sort's instability is easy to see concretely. In [(2,a), (2,b), (1,c)], pass 1 swaps the 1 into position 0, which throws (2,a) to where (1,c) was — now behind (2,b).

Any unstable sort can be made stable by appending the original index to each key as a tiebreaker. It costs O(n) memory, which is often exactly the memory you were using an in-place sort to avoid.

Comparison Table

Footnotes that matter:

• Bubble's O(n) best case requires the early exit. Without it, it is O(n²) on every input.
• Quick sort's O(log n) space is recursion stack, and only if you recurse into the smaller side first. Naive implementations are O(n) in the worst case.
• Merge sort's O(n) space drops to O(1) for linked lists.
• Counting sort's k is the value range, not the input size. It is only linear when k = O(n).

What Java Actually Runs

Calling Arrays.sort() does not run any of the textbook algorithms unmodified.

For objects (and Collections.sort()), Java uses TimSort a hybrid of merge sort and insertion sort, written by Tim Peters for Python in 2002 and adopted by Java in Java 7.

TimSort's insight is that real data is rarely random. It contains runs of already-ordered elements. TimSort finds those natural runs, extends short ones with insertion sort (the threshold is 32 elements), then merges the runs with a merge sort that maintains a stack of pending merges. On already-sorted input it finds one run and finishes in O(n).

Objects get a stable sort because for objects, stability is observable and useful two records can be equal by the comparator and still be different objects.

For primitives (int[], double[]), Java uses Dual-Pivot Quicksort, also since Java 7. Two pivots split into three partitions rather than two, which reduces the number of passes. It falls back to insertion sort for small ranges and has heuristics to detect and escape bad pivot patterns.

Why not TimSort for primitives? Because stability is meaningless for them one int with value 5 is indistinguishable from another. With nothing to preserve, you may as well take quicksort's speed and skip merge sort's O(n) memory.

Integer[] objects = {5, 3, 8, 1, 2};
Arrays.sort(objects);          // TimSort: stable, adaptive, O(n) memory

int[] primitives = {5, 3, 8, 1, 2};
Arrays.sort(primitives);       // Dual-pivot quicksort: in-place, not stable

List<Integer> list = new ArrayList<>(List.of(5, 3, 8, 1, 2));
Collections.sort(list);        // delegates to List.sort -> Arrays.sort -> TimSort

That one API making two different choices, purely on whether stability is observable, is a neat summary of this whole post.

Which One to Use

flowchart TD
    S(["need to sort"]) --> LIB{"standard library<br/>available?"}
    LIB -->|"yes"| USE(["use Arrays.sort<br/>or Collections.sort"])
    LIB -->|"no, or special case"| K{"small integer<br/>value range?"}
    K -->|"yes"| CS(["counting / radix sort<br/>O(n + k)"])
    K -->|"no"| SM{"fewer than<br/>~50 elements?"}
    SM -->|"yes"| INS(["insertion sort"])
    SM -->|"no"| ST{"stability<br/>required?"}
    ST -->|"yes"| MS(["merge sort"])
    ST -->|"no"| MEM{"memory<br/>tight?"}
    MEM -->|"yes"| QS(["quick sort<br/>+ good pivot"])
    MEM -->|"no"| MS
    classDef pick fill:#008987,stroke:#00605f,color:#ffffff
    class USE,CS,INS,MS,QS pick

Use the standard library. This is the real answer almost every time. Arrays.sort and Collections.sort are battle-tested, handle every edge case, and are faster than what you will write. Understand the algorithms so you can reason about their behaviour, not so you can reimplement them.

Insertion sort for small or nearly-sorted data, or as the base case inside a bigger algorithm.

Merge sort when you need guaranteed O(n log n), when you need stability, or when sorting a linked list.

Quick sort when memory is tight and you do not need stability with a randomised or median-of-three pivot, never a naive first/last one.

Counting or radix sort when keys are integers in a small known range. This is the only way to beat n log n.

Avoid bubble and selection sort in production. Selection sort's minimal-write property is the only argument for either, and it is a narrow one.