Lesson 14.1 · Sorting and Divide & Conquer

Sorting Basics: Stability and the n log n Limit

Simple sorts are O(n²); good comparison sorts are O(n log n), which is provably the best possible; stability decides whether equal items keep their order.

14 min

Think of it like this

Sorting a hand of playing cards: most people pick up one card at a time and slide it into place among the cards already held. That's insertion sort: great for a handful of cards, painfully slow for a whole deck shuffled into a pile of thousands.

1.Insertion sort, the simplest good-enough sort

Grow a sorted prefix: take the next element and shift larger elements right until its place is found. O(n²) in the worst case, but O(n) on nearly sorted data, which is why real libraries use it for small pieces.

▶ Dry run: Insertion sorta = [5, 2, 4, 1]

Step 1/4[5] alone is sorted.

2.Why comparison sorts can't beat n log n

A sort that only compares elements must distinguish all n! possible input orders. Each comparison has two outcomes, so it needs at least log₂(n!) ≈ n log₂ n comparisons in the worst case. Merge sort and heap sort meet that bound.

Counting and radix sorts beat it by not comparing: they use the values themselves as positions, which only works for small integer ranges or fixed-width keys.

3.Stability

A stable sort keeps equal elements in their original order. That matters when you sort by one key after another (sort by name, then stably by city: names stay in order within each city). Java's Arrays.sort on objects (TimSort) and Collections.sort are stable; on primitives it uses dual-pivot quicksort, which isn't, but equal primitives are indistinguishable anyway.

Stable.java

import java.util.*;

public class Main {
    record Order(String customer, String city) {}

    public static void main(String[] args) {
        List<Order> orders = new ArrayList<>(List.of(
            new Order("Arjun", "Pune"), new Order("Meera", "Guwahati"),
            new Order("Priya", "Pune"), new Order("Dev", "Guwahati")));
        orders.sort(Comparator.comparing(Order::city));     // stable: original order kept within a city
        for (Order o : orders) System.out.println(o.city() + " " + o.customer());
    }
}

Output

Guwahati Meera
Guwahati Dev
Pune Arjun
Pune Priya

Remember

Insertion sort: O(n²), great for small or nearly sorted input.
Comparison sorts need Ω(n log n) comparisons.
Stable sorts keep equal items in order; Java's object sort is stable.

Common mistakes

Assuming every sort is stable.
Thinking a clever comparison sort can be O(n).

Command Palette

Sorting Basics: Stability and the n log n Limit

1.Insertion sort, the simplest good-enough sort

2.Why comparison sorts can't beat n log n

3.Stability