← Sorting · guided lesson
Sorting
the story
Insertion sort (and the other O(n²) sorts)
Every tool here exists because something was too slow or broke without it. Here is what.
The simple sorts are older than their names. In 1956 E. H. Friend's survey in the Journal of the ACM compared methods such as inserting and exchanging — and found exchanging needs at least twice as many comparisons as inserting. Owen Astrachan's 2003 history of bubble sort found early books calling it "exchange sorting"; the first use of the name bubble sort in print he could find is Iverson's 1962 book A Programming Language. Knuth's verdict: bubble sort "seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems".
the problem it solved
Sorting small amounts of data on early machines with almost no spare memory — and, today, finishing tiny or nearly sorted ranges faster than any O(n log n) sort can.
why it matters: without it
Library sorts would waste recursion and bookkeeping on 5-element ranges, and nearly sorted data would cost as much as random data.
sources: Friend — Sorting on Electronic Computer Systems (Journal of the ACM 3(3), 1956) ↗ · Astrachan — Bubble Sort: An Archaeological Algorithmic Analysis (SIGCSE 2003) ↗ · Knuth — The Art of Computer Programming, Vol. 3: Sorting and Searching, §5.2.1–5.2.2 ↗
also in this chapter: Merge sort · Quicksort · Quickselect · Counting sort · Radix sort · TimSort (Java's object sort) · Dual-pivot quicksort (Java's primitive sort) · The Ω(n log n) limit for comparison sorts
the idea
The idea in 30 seconds
Sorting puts equal and nearby values next to each other — duplicates, overlaps and gaps become neighbours you can see in one pass.
Simple sorts compare neighbours and cost O(n²). Divide and conquer (merge, quick, heap) gets to O(n log n) — the best any comparison sort can do.
If values are small integers you can skip comparisons entirely and count them in O(n + k).
picture this
Clicking a column header in File Explorer or Excel: no row changes, only the order does — and suddenly the biggest file is on top, duplicate names sit together, and a missing invoice number jumps out. Sorting is that click, done in code.
watch it
Bubble sort — the biggest value bubbles right
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Bubble sort — the biggest value bubbles right
Neighbours swap until each pass parks the largest remaining value at the end (lime). A pass with no swaps ends the sort early.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Selection sort — pick the minimum, swap it to the front
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Selection sort — pick the minimum, swap it to the front
Always n(n−1)/2 comparisons, but at most n−1 swaps. Watch a long-distance swap break stability.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
Comparison sorts can't beat O(n log n) in the worst case: n! possible orders need at least log₂(n!) ≈ n log n yes/no questions to tell apart.
key idea 2 of 8
Read it once. Say it out loud once. Bas.
Stable = equal keys keep their original order. It matters when you sort records by one field after another (sort by name, then stably by age).
key idea 3 of 8
Read it once. Say it out loud once. Bas.
In-place = O(1) (or O(log n)) extra memory. Merge sort is not in-place on arrays; quick and heap sort are.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
Adaptive = faster on nearly-sorted input. Insertion sort (and TimSort, built on it) runs in O(n) on sorted data.
key idea 5 of 8
Read it once. Say it out loud once. Bas.
Quicksort is fastest in practice but O(n²) with bad pivots — random pivots make that vanishingly unlikely; median-of-three helps on ordinary data, but crafted inputs can still force it.
key idea 6 of 8
Read it once. Say it out loud once. Bas.
Merge sort is O(n log n) always, stable, and is the sort for linked lists and for counting things like inversions.
key idea 7 of 8
Read it once. Say it out loud once. Bas.
Java: Arrays.sort(int[]) = dual-pivot quicksort (not stable, no one can tell equal ints apart). Arrays.sort(Object[]) / Collections.sort = TimSort, stable.
key idea 8 of 8
Read it once. Say it out loud once. Bas.
Never write (a, b) -> a - b — it overflows. Use Integer.compare(a, b) or Comparator.comparingInt(...).
spot the pattern
When you see this, think this
Intervals, meetings, schedules — anything with start/end
Sort by start (or end), then sweep once
"Find duplicates / closest pair / group equal things"
Sort so equal or near values become neighbours
Pair or triplet sums without needing original indices
Sort + two pointers
"k-th largest / smallest", "top k"
Quickselect (O(n) avg) or a size-k heap (O(n log k))
+4 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Comparator
(a, b) -> a - boverflows for large or negative values. UseInteger.compareorcomparingInt. Arrays.sort(int[], Collections.reverseOrder())doesn't compile — comparators only work on object arrays likeInteger[].
quick check
One question. No pressure.
Which sort is fastest on an array that is already sorted?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Sort an Array
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Why can't any comparison sort beat O(n log n) in the worst case?
Question 1: Why can't any comparison sort beat O(n log n) in the worst case?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.