Searching and Sorting Reconstructed

Each algorithm in Part III is presented as an algorithm card: the problem, the conventional algorithm with pseudocode and a correctness argument, its costs, a pointer to its SDK implementation, its CGT reading (which grammar it operates on, and how grammar operations map to implementation steps), and — always — where the grammatical view adds nothing. This chapter’s verdict is mostly equivalence: sorting and searching are the home ground of classical algorithm design, and the grammatical view re-describes them without making them faster. That verdict is itself a result.

9.1 Searching

Problem. Given a sequence $a_0, \dots, a_{n-1}$ and a value $x$, find an index $i$ with $a_i = x$, or report that none exists.

lo ← 0; hi ← n                      invariant: a[lo-1] < x ≤ a[hi]  (sentinels a[-1] = −∞, a[n] = +∞)
while lo < hi:
    mid ← ⌊(lo + hi)/2⌋
    if a[mid] < x: lo ← mid + 1 else: hi ← mid
return lo if lo < n and a[lo] = x else −1

SDK: cgtsdk.algorithms.binary_search, linear_search. Grammar: binary search is navigation in the implicit balanced search tree whose root is the middle element: each comparison is a move $L$ or $R$, and the comparison outcomes spell the address of the answer. The sorted array is a perfectly balanced BST in disguise, with addresses computed by midpoint arithmetic — arithmetic addressing again (M-ARITH). Where grammar adds nothing: the algorithm is optimal among comparison-based searches (an adversary argument gives $\lceil \log_2(n+1) \rceil$), and no re-description changes that.

9.2 Four comparison sorts

Problem. Rearrange a sequence into non-decreasing order.

The four classical comparison sorts, in their SDK form:

for i ← 1 to n−1:                    invariant: a[0..i) is sorted
    x ← a[i]; j ← i − 1
    while j ≥ 0 and a[j] > x: a[j+1] ← a[j]; j ← j − 1
    a[j+1] ← x

The invariant gives correctness at once. The comparison count is $n - 1$ plus the number of inversions (pairs $i < j$ with $a_i > a_j$), capped per element by its position — exactly $n - 1$ on sorted input and $n(n-1)/2$ on reversed input. The SDK counts confirm both exactly:

import random
from cgtsdk import Cost
from cgtsdk.algorithms import heapsort, insertion_sort, merge_sort, quicksort

n = 512
inputs = {"sorted": list(range(n)), "reversed": list(range(n, 0, -1)),
          "random": random.Random(1).sample(range(10**6), n)}
print(f"{'input':9s} {'insertion':>10s} {'merge':>7s} {'heap':>7s} {'quick':>7s}   n(n-1)/2={n*(n-1)//2}  n*log2(n)={n*9}")
for name, a in inputs.items():
    counts = []
    for f in (insertion_sort, merge_sort, heapsort, quicksort):
        c = Cost(); assert f(a, c) == sorted(a); counts.append(c.counts.get("compare", 0))
    print(f"{name:9s} {counts[0]:10d} {counts[1]:7d} {counts[2]:7d} {counts[3]:7d}")

input      insertion   merge    heap   quick   n(n-1)/2=130816  n*log2(n)=4608
sorted           511    2304    7958    8642
reversed      130816    2304    7203    8217
random         69565    3970    7599    7796

(Quicksort here uses a three-way partition that charges up to two comparisons per element per partitioning step, which is why its counts sit above merge sort’s.) Insertion sort is the best of the four on sorted input and by far the worst on reversed input; merge sort makes exactly $n \log_2 n / 2 = 2304$ comparisons when one half always wins, and fewer than $n \lceil \log_2 n \rceil = 4608$ in every case.

9.3 The comparison lower bound as a statement about grammar

A comparison sort can learn about its input only by comparing elements. Its execution on all inputs of size $n$ is therefore described by a decision tree: a binary tree whose internal nodes are comparisons “$a_i < a_j$?” and whose leaves are output permutations. Each run follows one root-to-leaf path; the path’s address — the word of comparison outcomes — determines the output.

In the language of this book: the grammar available to a comparison sort is the binary alphabet of comparison outcomes, and the information it must produce is one of $n!$ answers. No grammar over a two-letter alphabet can address $n!$ answers with words shorter than $\log_2 n!$. This is the counting lemma that reappears in Chapter 12 as an information lower bound on any precomputed grammar (CGT-THM-002). Re-describing sorting grammatically cannot beat it — and claims to “sort in constant time with a grammar” should be read against it.

9.4 Counting sort: escaping the bound by arithmetic addressing

The lower bound assumes that comparisons are the only way to learn about the input. If the keys are integers in a small range $[0, k)$, a key can be used as an address:

count[0..k] ← 0
for x in a: count[x+1] ← count[x+1] + 1          histogram, using x as an address
for i ← 0 to k−1: count[i+1] ← count[i+1] + count[i]   prefix sums: first slot of each key
for x in a (left to right): out[count[x]] ← x; count[x] ← count[x] + 1   stable placement

This is mechanism M-ARITH in its purest form: the key’s value is the location, exactly like an array index (Chapter 2). And it has exactly the array’s limitation: the density $n / k$ must not be small. With $k = \Theta(n)$ it is linear; with 64-bit keys ($k = 2^{64}$) it is absurd. Radix sort refines the idea by addressing one digit at a time.

import random
from cgtsdk import Cost
from cgtsdk.algorithms import counting_sort, merge_sort

rng = random.Random(2)
for n, k in ((10_000, 100), (10_000, 10_000), (10_000, 1_000_000)):
    a = [rng.randrange(k) for _ in range(n)]
    c1, c2 = Cost(), Cost()
    assert counting_sort(a, k, c1) == merge_sort(a, c2) == sorted(a)
    print(f"n={n} k={k:9d}  counting sort: {c1.total:9d} steps, 0 comparisons   merge sort: {c2.total:7d} steps")

n=10000 k=      100  counting sort:     50301 steps, 0 comparisons   merge sort:  253841 steps
n=10000 k=    10000  counting sort:     80001 steps, 0 comparisons   merge sort:  254082 steps
n=10000 k=  1000000  counting sort:   3050001 steps, 0 comparisons   merge sort:  254093 steps

At density $100$ keys per slot, counting sort is five times cheaper than merge sort in counted steps; at density $10^{-2}$ it is twelve times more expensive. The same algorithm wins or loses according to a single structural parameter — the density of the address space.

9.5 Verdict

For searching and sorting, the grammatical view gives re-descriptions: binary search as navigation in an implicit tree, a sorting algorithm as a grammar of comparison outcomes, counting sort as arithmetic addressing. It gives no speedup over the classical algorithms, and the comparison lower bound explains why none is possible within the comparison model. What it does give is a uniform vocabulary in which the one known way around the bound — using keys as addresses — is the same mechanism as array indexing and heap navigation, with the same failure condition.

Report an erratum or an unclear passage in this chapter