[algorithm] sleep sort

UPDATED: đã update phiên bản viết bằng golang ở cuối bài.
Ngày hôm nay,  cộng đồng hackernews điên đảo vì một thuật toán sắp xếp được phát minh từ năm 2011 do một người ẩn danh đưa ra với tên gọi "sleep sort".

Nguyên văn implement trên bash như sau:


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

example usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7

Chỉ cần google là bạn sẽ tìm thấy nguồn, bài viết này sẽ không link đến trang mà thuật toán này được công bố, đơn giản vì không thích. Nếu lười gõ google, bạn có thể bấm vào đây.

Thuật toán khá dễ hiểu, có thể mô tả bằng lời như sau: chương trình nhận nhiều tham số đầu vào
(arguments), với mỗi số đầu vào, ví dụ số đó là N, chạy một process con (subprocess) ở chế độ background (tức chương trình sẽ tiếp tục chạy sau khi tạo 1 subprocess chứ không đợi subprocess này kết thúc), sleep N giây rồi in ra số N.
Hiển nhiên với đầu vào là 2, 1, 3, chương trình

1. đọc số 2, đợi 2 giây rồi in ra số 2
2. đọc số 1, đợi 1 giây rồi in ra số 1
3. đọc số 3, đợi 3 giây rồi in ra số 3

vì thời gian đọc vào cả 3 số gần như tức thời, mà đợi 1 giây nhanh hơn đợi 2 giây nên số 1 được in ra trước, rồi đến số 2, rồi số 3 ... và mọi thứ được sắp xếp tăng dần.
Đây không phải một thuật toán có kết quả tốt (nhanh) vì nếu có một số ở input là 1000, bạn phải đợi 1000 giây. Nhưng ý tưởng rất vui, khơi dậy rất nhiều vấn đề liên quan đến việc quản lý process, hàm sleep, và thậm chí gây rất nhiều tranh cãi về độ phức tạp thuật toán O(n).

Nếu bạn không thấy vui? có thể đọc phần tranh cãi về cách tính O(n) cho thuật toán này cho bớt không vui.
Nếu vẫn không thấy vui? đến giờ đi ngủ rồi !

Hết.
hvn@familug.org

PS: phiên bản lược bỏ phần parse argument  trên golang