Melhor resposta
A classificação de sono é um algoritmo de classificação de piadas que se tornou popular na placa 4chan / prog / [1]. O pseudocódigo para classificação sleep é:
procedure printNumber(n)
sleep n seconds
print n
end
for arg in args
run printNumber(arg) in background
end
wait for all processes to finish
Ha-ha! Hilariante .
Em outras palavras, o que acontece é que a classificação sleep gera um processo para cada argumento. Cada processo espera por n segundos e, em seguida, imprime n, o que significa que leva 1 segundo para imprimir “1” e 2 segundos para imprimir saída “2”, 100 segundos para imprimir “100”. Isso significa que, na maior parte, os números são impressos na ordem de seu tamanho, “classificando” os argumentos.
A complexidade desse algoritmo em um mundo perfeito é O(max(args)), pois levará max(args) segundos para imprimir o maior arg. Na realidade, a complexidade é O(n^2 + max(args)), porque a manutenção de vários processos em segundo plano depende do sistema operacional para gerenciar a alternância de contexto e a priorização dos processos e, portanto, o algoritmo basicamente terceiriza a classificação real para o kernel.
Observe também que não há garantias de que a saída da classificação esteja realmente correta, um recurso que a maioria dos outros algoritmos de classificação não tem.
[1] http://dis.4chan.org/read/prog/1295544154
Resposta
Apenas por diversão, há implementação em Erlang
sort(L) ->
Parent = self(),
[ spawn\_link(fun() -> receive after X*10 -> Parent ! X end end) || X <- L ],
[ receive X -> X end || \_ <- L ].
Que pode ser escrita muito bem como uma expressão no shell Erlang também
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].