Who Decided What Sorted Is?

Sorting · Part 3 of 7

Stop comparing. Start counting. The data already knows where it belongs. (#1 of 12 by total time in the unified benchmark)

Series: 1 · Disorder Clusters | 2 · The C Revelation | 3 · Who Decided What Sorted Is | 4 · Why Look When You Can Just Do | 5 · Where the Thread Ends | 6 · Sieve Sort | 7 · The Pendry Sort Paper

Imagine you're walking on a beach. You stumble on a line of sand grains arranged perfectly by size. You stare at it. You marvel at how sorted that line is. You call people over to look.

Meanwhile, the entire beach sits there, billions of grains, each one exactly where physics put it. Wind, water, gravity, and time placed every grain precisely where it needs to be. Nobody sorted the beach. The beach sorted itself. Every grain settled.

But you're staring at the one line, asking: is grain A smaller than grain B? Is B smaller than C?

You're asking the wrong question.

The wall: The theoretical floor for comparison sorts is O(n log n). Proven, mathematical, absolute. But that wall only exists if you're comparing. Counting sort runs in O(n + k) and ignores the wall entirely.

The Wrong Question

Every sorting algorithm I'd built up to this point asks the same thing: is this element less than that element? Safe-Slot Sort asks it more efficiently, only where disorder exists, but it still asks. Quicksort asks it. Merge sort asks it. Heapsort asks it. They're all comparison-based. They all impose an external judgment on data that might already know where it belongs.

What if you stopped comparing and started listening?

Gravity Sort

Heavy things sink. Light things float. Don't move anything. Just count what's there and let gravity stack it.

// Copyright 2026 HalfHuman Draft - Pendry, S
// Licensed under the Apache License, Version 2.0

void gravity_sort(int* a, int n) {
    if (n <= 1) return;
    int lo = a[0], hi = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] < lo) lo = a[i];
        if (a[i] > hi) hi = a[i];
    }
    if (lo == hi) return;
    int range = hi - lo + 1;
    int* weight = calloc(range, sizeof(int));
    for (int i = 0; i < n; i++) weight[a[i] - lo]++;
    int pos = 0;
    for (int w = 0; w < range; w++)
        for (int c = 0; c < weight[w]; c++)
            a[pos++] = w + lo;
    free(weight);
}

Two passes. First pass: weigh everything, count how many of each value exist. Second pass: stack them from lightest to heaviest. Gravity did the work. We just watched.

Echo Sort was the same math with a different metaphor: the data is a room full of voices, each element shouts its value, you listen to the echoes lowest to highest. Same algorithm wearing different philosophical hats. Both are O(n + range), where range is the span of values. They break the O(n log n) floor because they never compare. They count.

The admission: Gravity Sort and Echo Sort are the same algorithm. This was the first time I rediscovered something by giving it a new name. It happened again with CAS in Post 4. Metaphors can fool you.

Gravity Sort: #1 by Total Time

Counting sort. O(n + k) time, O(k) space, zero comparisons. Tested on 34 of 35 patterns (N/A only on Uniform [-1B, 1B] where the frequency array would be 8 GB).

Gravity Sort vs Every Competitor (1M elements)

Aggregate

Why It Wins

Gravity Sort takes the #1 spot in the unified C benchmark by total time: 241,526 microseconds across 34 patterns. Pendry Sort is second at 359,174 microseconds. Radix-256 is third at 897,877 microseconds. Everything else is over a million.

The reason is structural. On 33 of the 34 patterns where Gravity runs, the value range is at most n (1,000,000). That puts it squarely in counting sort's optimal regime. Two linear passes through the data plus one linear pass through the frequency array. No comparisons, no branches in the hot path, sequential memory access patterns that the CPU prefetcher loves.

It doesn't care about corruption. 0% scatter: 7.2ms. 100% scatter: 7.2ms. It literally cannot tell the difference because it's counting, not comparing. It doesn't notice the shape because it never asks about shape.

The pipe organ result is the standout: qsort hits 241.9ms on ascending-then-descending data, which is near worst-case for quicksort's pivot selection. Gravity does it in 6.2ms. 39x faster, without even noticing the pattern.

Cache behavior: Two sequential reads over n elements, one sequential write over k elements, one sequential write over n elements. Every access is sequential. Modern CPUs prefetch sequential memory automatically. This is why counting sort's constant factor is so small despite its O(n + k) theoretical cost.

The Honest Limitations

Gravity Sort has one constraint that comparison sorts don't: it needs the value range to fit in memory. It allocates an array of size (max − min + 1). For integer data where range ≤ 4n, this is cheap. For data spanning [-1 billion, 1 billion] with only a million elements, the frequency array would be 8 GB. That's the one N/A pattern in the benchmark: Uniform [-1B, 1B].

The benchmark also reveals something the original post didn't emphasize enough: Gravity Sort is not the fastest algorithm on any single pattern where Pendry Sort also runs. On sorted data, Pendry is faster (1.6ms vs 7.2ms). On nearly-sorted local swaps, CAS-Core is faster (1.3ms vs 7.2ms). On heavy dupes, Pendry edges it (4.8ms vs 4.9ms). Gravity wins on aggregate because it runs on almost everything and is consistently good. It's the tortoise, not the hare. It wins the race by never stopping.

Three Philosophies

At this point in the series, three fundamentally different answers to "what is sorting?" had emerged:

Gravity/Counting: Sorting is observation. The data already knows where it belongs. Stop rearranging and start counting. The beach was never unsorted.

Micro SSS / CAS: Sorting is repair. The data has structure. Most of it is fine. Find what's broken and fix just that. Don't tear down the house because one window is cracked.

Traditional comparison sorts (qsort, introsort, heapsort): Sorting is judgment. Compare everything against everything else. Assume nothing. Trust nothing. Rebuild from scratch.

Each philosophy has a domain where it's unbeatable. And each has a domain where it falls apart. The benchmark quantifies both.

Everything is a number: A poem is a sequence of words with dictionary positions. A database row has a primary key. A color is a wavelength. Once you have a mapping function, everything is countable. And once it's countable, comparison is optional.

Classification

When to use it: You have integer data, the value range is reasonable relative to the element count, and you want raw speed regardless of input shape. It doesn't care about corruption, patterns, direction, or duplicates. It counts and stacks.

When to use something else: Your data has a wide range, you need generic type support, or you need stability (preserving original order of equal elements). For wide-range integers, Post 5 builds a bucket scatter approach. For generic types, Sieve Sort handles anything comparable.

Previously: The C Revelation — 18x speedups and the three tenets.

Next: Why Look When You Can Just Do? — CAS, insertion sort, and the honesty of rediscovery.