Sorting and searching

Which comparison sort to reach for, why stability matters, and binary search written so it cannot loop forever.

Comparison sorts

def quicksort(a, lo=0, hi=None):
    """In place, average O(n log n). The pivot choice decides the worst case."""
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return a
    pivot = a[(lo + hi) // 2]              # middle element: safer than a[lo]
    i, j = lo, hi
    while i <= j:
        while a[i] < pivot:
            i += 1
        while a[j] > pivot:
            j -= 1
        if i <= j:
            a[i], a[j] = a[j], a[i]
            i, j = i + 1, j - 1
    quicksort(a, lo, j)                    # recurse on the smaller side first
    quicksort(a, i, hi)
    return a


def merge_sort(items):
    """Stable, guaranteed O(n log n), O(n) extra space."""
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left, right = merge_sort(items[:mid]), merge_sort(items[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:            # <= keeps equal keys in input order
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out


# Real code should just call the built-in: Timsort is O(n) on sorted runs
records.sort(key=lambda r: (r['city'], -r['score']))

• A comparison sort cannot beat O(n log n) in the worst case; counting and radix sort escape that bound only by not comparing keys.
• Stability means equal keys keep their input order, which is what makes multi-key sorting work: sort by the least significant key first, then stably by the most significant.
• Quicksort's worst case is O(n²) on already-sorted input with a first-element pivot; randomised or median-of-three pivots make that adversarial case very unlikely.
• Insertion sort is the right answer for small arrays, which is why production sorts switch to it below roughly ten to twenty elements.
• Counting sort needs a small integer key range; a range of a billion makes the bucket array itself the problem.

Binary search

Binary search halves the search space each step, so a million sorted items take about twenty probes. It requires random access: on a linked list, reaching the middle item is already O(n), which destroys the saving.

import bisect

def binary_search(sorted_items, target):
    """Return the index of target, or -1. Half-open range [lo, hi)."""
    lo, hi = 0, len(sorted_items)
    while lo < hi:
        mid = (lo + hi) // 2
        if sorted_items[mid] == target:
            return mid
        if sorted_items[mid] < target:
            lo = mid + 1                   # mid is excluded, so progress is safe
        else:
            hi = mid
    return -1

def first_at_least(sorted_items, target):
    """Lower bound: the first index whose value is >= target."""
    lo, hi = 0, len(sorted_items)
    while lo < hi:
        mid = (lo + hi) // 2
        if sorted_items[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo                              # may equal len(sorted_items)

sorted_items = [1, 3, 3, 5, 8]
print(binary_search(sorted_items, 5))          # 3
print(first_at_least(sorted_items, 3))         # 1
print(bisect.bisect_left(sorted_items, 3))     # 1  - the same thing, in C
print(bisect.bisect_right(sorted_items, 3))    # 3  - one past the last 3

# Rotated sorted array: still O(log n) if you drop one sorted half per step
def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:              # left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                  # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Beyond sorted lists

• Interpolation search probes where the target is likely to be and is faster on uniformly distributed keys, but degrades to O(n) on clustered data.
• Exponential search finds the range by doubling and then binary searches it: O(log n) over an unbounded or streaming sequence.
• A sorted list plus binary search is excellent for a static dataset. Once inserts arrive, the O(n) shift on every insert makes a balanced tree or a B+tree the better structure.
• Searching a text file line by line is O(n) per query. An inverted index does the same work once, turning each query into a lookup.
• For repeated membership tests on an unsorted collection, a set is O(1) per query and beats binary search plus the O(n log n) sort it requires.

import heapq

# Top-k of a stream without sorting a million items: O(n log k)
def top_k(stream, k):
    heap = []
    for item in stream:
        if len(heap) < k:
            heapq.heappush(heap, item)
        elif item > heap[0]:
            heapq.heapreplace(heap, item)   # drop the smallest of the best so far
    return sorted(heap, reverse=True)

print(top_k(range(1000), 3))                # [999, 998, 997]

# Two sorted lists into one: O(n + m) beats concatenate-and-sort at O((n+m) log(n+m))
def merge_sorted(a, b):
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    return out + a[i:] + b[j:]

FAQ

Related

Complexity and Big-O in practice Graph algorithms: BFS, DFS and shortest paths

Last refreshed 2026-09-18.