Sorting and searching

Binary search is how you look a word up in a dictionary: open in the middle, decide whether the word is before or after, repeat in the half that remains.

Every comparison halves the search area. That gives $\log_2 n$ steps:

A billion elements in thirty comparisons. The condition is that the list is sorted.

Merge sort builds on the same halving idea, backwards: split the list in two, sort each half (recursively), and merge the two sorted halves. Merging two sorted lists is easy — compare the front elements and take the smaller one.

That gives $O(n\log n)$: $\log n$ levels of splitting, and $n$ work at each level.

The common algorithms:

Stable means that elements with equal keys keep their relative order. It matters when you sort in several steps: sort first on the first name, then on the surname — with a stable sort, people with the same surname end up sorted by first name.

Python's sorted is Timsort, a hybrid that looks for already sorted stretches («runs») and merges them. On partly sorted data — which real data often is — it becomes nearly linear.

When does it pay to sort first? Sorting costs $O(n\log n)$ once, and after that each search costs $O(\log n)$ instead of $O(n)$. With $k$ searches:

$\underbrace{n\log n + k\log n}_{\text{sort first}} \quad\text{against}\quad \underbrace{kn}_{\text{linear search}}$

With $n = 10^6$: a single search → do not sort. A thousand searches → sort.

But in Python the answer is usually a different one: if all you need is «is this in there?», a set is better still — O(1) per question, no sorting. Sorting is needed when you want order, ranges («everything between 10 and 20») or the nearest value.

The classic bug in binary search is while left < right instead of <=, or updating the bounds to mid instead of mid ± 1. The first misses the last element; the second gives an infinite loop. Both are easy to write and hard to see.

def binary_search(sorted_items, target):
    lo, hi = 0, len(sorted_items) - 1
    while lo <= hi:                        # <= : otherwise the last element is missed
        mid = (lo + hi) // 2
        if sorted_items[mid] == target:
            return mid
        if sorted_items[mid] < target:
            lo = mid + 1                   # mid + 1, not mid — otherwise an infinite loop
        else:
            hi = mid - 1
    return -1

def merge_sort(x):
    if len(x) <= 1:
        return x
    m = len(x) // 2
    return merge(merge_sort(x[:m]), merge_sort(x[m:]))

def merge(a, b):
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:                   # <= makes the sort stable
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    return out + a[i:] + b[j:]

print(binary_search([1, 3, 5, 7, 9, 11], 9))   # 4
print(binary_search([1, 3, 5, 7, 9, 11], 4))   # -1
print(merge_sort([5, 2, 9, 1, 5, 6]))          # [1, 2, 5, 5, 6, 9]

# Stability in practice: sort in two steps
pupils = [("Svensson", "Bo"), ("Andersson", "Cim"), ("Svensson", "Ada")]
step1 = sorted(pupils, key=lambda e: e[1])          # the first name
step2 = sorted(step1, key=lambda e: e[0])           # the surname — stable
print(step2)
# [('Andersson', 'Cim'), ('Svensson', 'Ada'), ('Svensson', 'Bo')]

# In practice: use the standard library
import bisect
items = [1, 3, 5, 7, 9]
print(bisect.bisect_left(items, 5))           # 2 — the index where 5 starts
print(bisect.insort(items, 6) or items)       # [1, 3, 5, 6, 7, 9]