Sleep Sort

Usually, the only content coming from open-message-board extravaganza 4chan is … questionable, at best, but someone pitched a sorting algorithm that’s trivial, beautiful and a bit unique: Sleep Sort. Bonus points for having a great lazy name, and it does work. It basicly forks a process and lets it sleep for n seconds, where n is the current number to be sorted. The final output is a sorted array of numbers. You can pick the timeticks smaller than seconds, and voila.

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

When it comes to complexity, it’s actually a cleverly disguised bucket sort, with an average case complexity of O(n+m) with m the largest number in the sequence and n the amount of elements. Am I wrong? Discuss!

Leave a Reply