Commissioned for this museum · after an anonymous internet post of 2011

Sorted by Waiting

Shell·2011·15 lines·239 bytes

#!/usr/bin/env bash
#
# Sort a list of numbers without comparing any two of them.

sleepsort() {
    for n in "$@"; do
        (
            sleep "$n"
            printf '%s\n' "$n"
        ) &
    done
    wait
}

sleepsort 5 3 9 1 7 2 8

Curator’s note

No two numbers are ever compared. There is no < anywhere, and there is nothing that could be called a comparison hiding under another name. Each number is handed to a separate process which waits that many seconds and then says its own name, and the answers arrive in order because waiting longer happens later.

The sort has been moved out of the program and into the operating system. What is doing the work is the scheduler — a thing built to decide which process runs next, pressed into service as a comparator it does not know it is being.

It really does sort, which is the uncomfortable part. Run it on 5 3 9 1 7 2 8 and nine numbers come back in order. It is also useless, and interestingly so. It cannot sort anything that is not a number. It takes as long as its largest element, so sorting a list containing one million takes eleven days. It silently gives the wrong answer for values close together, because the promise sleep makes is "at least this long", not "exactly". And it needs one process per element, so a long list exhausts the machine rather than the clock.

Set beside a sort somebody would actually use it makes a point about what an algorithm is allowed to assume. Quicksort assumes only that any two things can be compared. This assumes the passage of time.

It appeared anonymously on an internet forum in 2011.