Sorting & Binary Search: Order Is a Superpower

What you'll learn

• Why sorted data is so valuable, and how the classic sorting algorithms work
• The difference between O(n²) sorts and O(n log n) sorts, and what stable means
• How to use your language's built-in sort with a comparator, and the classic bug that goes with it
• Binary search: finding anything in a sorted list of a million items in about 20 steps
• The lower-bound template that avoids off-by-one errors, and how to binary-search on an answer
• You will write: a leaderboard sort, a binary-search query engine and a merge sort that counts inversions

The bookshelf and the guessing game

Imagine a shelf of 1,000 books in random order. To find one title you must pick up books one by one: in the worst case, all 1,000. Now imagine the same shelf sorted by title. Open it in the middle: if your title comes before the one you see, ignore the right half, otherwise ignore the left half. Repeat. After about 10 looks you are standing at the book (2¹⁰ = 1,024).

It is the same as the guessing game "I'm thinking of a number from 1 to 1,000": the smart player says 500, hears "higher", says 750, and never needs more than 10 guesses. Every guess throws away half of the possibilities.

The price is that someone had to sort the shelf first. This lesson is about both halves of the deal: how to sort efficiently, and how to cash in on the order with binary search.

Sorting: the toolbox

The slow family, O(n²). Bubble, selection and insertion sort compare items in nested loops. For n = 1,000 that is about a million steps; for n = 1,000,000 it is about 10¹², far too slow. Insertion sort deserves a mention: it is O(n²) in the worst case but close to O(n) when the data is almost sorted, so real libraries use it for small pieces.

The fast family, O(n log n).

• Merge sort (divide and conquer): split the list in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front item. Always O(n log n), needs O(n) extra space, and is naturally stable.
• Quicksort: pick a pivot, partition into "smaller" and "larger", recurse on both. O(n log n) on average and very fast in practice, but a bad pivot choice (for example always the first item of already-sorted data) makes it O(n²).
• Heap sort: O(n log n) worst case with O(1) extra space (you will meet heaps later in this track).

How fast can any comparison sort be? A sort that only compares pairs of items needs at least about n log n comparisons in the worst case. You cannot do better, so O(n log n) is the practical target. If your keys are small integers you can beat it: counting sort runs in O(n + k) for keys in the range 0..k.

Stable sort: items with equal keys keep their original relative order. This matters when you sort twice: sort by name, then stable-sort by grade, and students with equal grades stay in alphabetical order.

In real life you call the built-in sort. Know what it guarantees:

• Python sorted() / list.sort(): stable (Timsort). JavaScript Array.prototype.sort: stable since ES2019. Rust slice.sort(): stable (sort_unstable is the faster, unstable one). Java Collections.sort and Arrays.sort on objects: stable.
• C++ std::sort: not stable; use std::stable_sort when you need it. Java Arrays.sort on primitive arrays: no stability concept, because equal ints are indistinguishable.

The comparator. To sort by your own rule you pass a function that returns a negative number if a goes first, positive if b goes first and 0 for a tie. Warning for JavaScript: without a comparator, sort() compares items as text, so [10, 9, 1].sort() gives [1, 10, 9]. Always pass (a, b) => a - b for numbers.

Binary search

Binary search finds a value in a sorted array by repeatedly looking at the middle item and discarding the half that cannot contain the answer. Each step halves the search range, so a million items need at most about 20 steps (2²⁰ = 1,048,576): O(log n).

The one requirement is order. (More precisely: a yes/no question whose answer flips only once, from "no" to "yes". Sorted data gives you that for "is a[i] >= x?".)

Plain "find x" versions are famous for off-by-one bugs. Use one template for everything instead, the lower bound: the first index whose value is at least x (or n if there is none).

def lower_bound(a, x):
    lo, hi = 0, len(a)            # the answer is somewhere in [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] >= x:
            hi = mid              # mid might be the answer: keep it
        else:
            lo = mid + 1          # mid is too small: throw it away
    return lo

Why it is safe. The loop keeps one invariant: every item before lo is smaller than x, and every item at hi or after is at least x. The range shrinks on every step and ends with lo == hi, which is the boundary.

Everything else is a one-liner on top of it:

• Is x present? i = lower_bound(a, x), then i < len(a) and a[i] == x
• First occurrence of x: lower_bound(a, x)
• How many copies of x (integers)? lower_bound(a, x + 1) - lower_bound(a, x)
• Where would x be inserted to keep the list sorted? lower_bound(a, x) (Python's bisect.bisect_left, C++'s std::lower_bound)

Two details that bite.

• Overflow. In Java, C or C++ with 32-bit int, (lo + hi) / 2 can overflow when lo + hi exceeds 2³¹ - 1. Write lo + (hi - lo) / 2. (Python integers do not overflow, but the habit is free.)
• Duplicates. Plain "return when a[mid] == x" finds some copy. Lower bound finds the first one every time.

Binary search on the answer. The same template works without any array. Suppose you want the smallest x for which a yes/no check ok(x) is true, and you know that once it is true it stays true for larger x (for example "can the job be done with x workers?" or "is x² at least N?"). Binary-search over the range of possible x, calling ok(mid) instead of reading a[mid]. The demo below does exactly that.

Merge sort, and what the merge step knows

Here is merge sort in full. It is the cleanest example of divide and conquer: split, solve each half, combine.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= keeps equal items in order: stable
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]

Why O(n log n)? The list is halved about log₂ n times, and every level of the recursion merges n items in total. So the work is n per level times log n levels.

An inversion is a pair of positions i < j with a[i] > a[j]: two items that are in the wrong order relative to each other. A sorted array has 0 inversions; a reversed array of n items has n(n - 1) / 2. Inversions measure "how unsorted" the data is (for instance, how different two people's rankings of the same movies are).

Counting them naively takes O(n²) (check every pair). But merge sort can count them for free. When you merge two sorted halves and you take an item from the right half while k items are still waiting in the left half, that right item is smaller than all k of them. That is exactly k inversions, found in one step. Add them up over the whole recursion and you get the answer in O(n log n).

One caution: with n up to hundreds of thousands the count can exceed the range of a 32-bit integer, so use a 64-bit counter (long long, long) as a habit.

Summary

• Sorted data is a superpower. It enables binary search, easy duplicate detection, merging and many greedy algorithms.
• Simple sorts (bubble, selection, insertion) are O(n²); merge sort, quicksort (on average) and heap sort are O(n log n), which is also the best any comparison sort can do. In practice you call the built-in sort.
• Stable sorts keep equal items in their original order. Always give JavaScript's sort a numeric comparator.
• Binary search is O(log n): about 20 steps for a million items. Use the lower-bound template with a half-open range [lo, hi) and lo + (hi - lo) / 2.
• The same template can search an answer instead of an array whenever a yes/no check flips only once.
• Merge sort can count inversions while it merges, in O(n log n) instead of O(n²).

Practice next: use binary search to find the minimum capacity that ships all packages in D days (search on the answer), search for a value in a rotated sorted array, and implement quicksort with a random pivot. Then continue with Trees & Graphs.