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!