Sorting (and binary search) — cheat sheet

General CS fundamentals, no course slide source — written directly, same as 01-big-o-notation.md. At this level you're unlikely to be asked to implement these from scratch, but you should be able to describe how each works, its complexity, and whether it's stable.

Stability

A sort is stable if elements that compare as equal keep their original relative order. Matters whenever you sort by one key and want ties broken by original order (or by a previous sort) — this is exactly what Comparator.thenComparing relies on being consistent.

Simple O(n²) sorts

• Bubble sort: repeatedly scan the list, swapping any adjacent out-of-order pair; each full pass "bubbles" the largest remaining element to its correct position. Stop once a full pass makes no swaps. O(n²) time, O(1) extra space, stable.
• Selection sort: repeatedly find the minimum of the unsorted remainder and swap it into place at the front. O(n²) time, O(1) extra space, not stable (the swap can jump an equal element out of order).
• Insertion sort: build up a sorted section at the front one element at a time, inserting each new element into its correct position within that section (like sorting a hand of playing cards). O(n²) worst case, but O(n) if the input is already nearly sorted — genuinely fast on small or almost-sorted inputs. O(1) extra space, stable.

Efficient O(n log n) sorts (divide and conquer)

• Merge sort: split the list in half recursively down to single elements, then merge sorted halves back together in order. O(n log n) time, guaranteed even in the worst case; O(n) extra space (needs a buffer to merge into); stable.
• Quicksort: pick a pivot, partition the list into "less than pivot" and "greater than pivot," recursively sort each partition. O(n log n) average time, but O(n²) worst case (e.g. an already-sorted list with a naively-chosen pivot); typically O(log n) extra space (recursion stack); not stable; usually faster in practice than merge sort despite the worse worst case, due to better cache locality and no extra buffer.

What Java actually uses

Collections.sort() / Arrays.sort() on objects use a variant of Timsort (a hybrid of merge sort and insertion sort) — stable, O(n log n). Arrays.sort() on primitive arrays (int[], etc.) uses a dual-pivot quicksort variant instead — stability doesn't matter for primitives since there's no notion of "equal but distinct" objects to preserve order for.

Binary search

Not a sort, but pairs with one: find a target in an already-sorted collection by repeatedly halving the search range — check the middle element, discard the half that can't contain the target, repeat. O(log n) time, O(1) space (iterative) or O(log n) space (recursive, due to call stack). Requires sorted input; that's the whole reason to sort something in the first place, in a lot of real cases.

Interview framing

Likely questions: "what's the time complexity of X sort," "is it stable, does that matter here," "why would you pick quicksort over merge sort" (speed/space trade-off vs. worst-case guarantee), or a live-coding ask to implement bubble sort or binary search — both short enough to write from memory.