算法与计算机科学dis.4chan.org
睡眠排序
Sleep Sort
2011 — 2014，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这个页面是 4chan /prog/ 上著名的 Sleep Sort 讨论帖：给每个待排序数字启动一个线程，让它休眠与数值成正比的时间，再按线程醒来的顺序输出，看似就得到了排序结果。它本质上是把排序外包给操作系统的定时器和线程调度，是个荒诞但可运行的算法玩笑，也引发了关于并发、计时精度和排序复杂度的讨论。
为什么经久不衰：它用极简而滑稽的构造揭示了一个真问题：排序可以发生在内核调度器里；这种“把问题推给系统”的脑洞让它反复被提起，今天读来仍有启发。
HN 评论精选
Sleep Sort 把数值映射为睡眠时长，靠内核定时器唤醒顺序完成排序，本质上是利用内核的插入排序/优先级队列。
撇开4chan的讨论不谈，核心概念是：对每个元素休眠 n 个单位时间，其中 n 与元素在列表中的字典序位置线性相关。所谓“啊哈”在于，生成的线程会按字典序醒来或返回。基本上，把集合 L 变换到时间域，再收集回来时就得到排序结果。这是个有趣的结果；作为系统分析练习，研究定时器分辨率、线程创建和顺序的影响也很有启发性，但最终这个“把戏”是你利用了内核在 sleep 事件上做的插入排序。你还可以试试它的近亲“priority sort”：创建线程并把优先级设为与元素值相关，最后让出 CPU，线程就会按优先级顺序打印内容——但排序仍然发生在内核把线程按优先级插入运行队列的时候。
ChuckMcM查看英文原文
4chan discussion aside, the concept here is that you 'sleep' n units of time for each element, where n is linearly related to the lexical relationship of the element to the other elements in the list. The 'aha' was that the resulting threads will 'wake up' or 'return' in lexical order. Basically if you transform set L into the time domain, when collecting it back you get it back sorted. Its a fun result, and as an exercise in systems analysis it can be enlightening to look at the impact of timer resolution, thread creation, and ordering, but ultimately the 'trick' is that you've exploited the 'insertion sort' that the kernel does on sleep events. You could try its close cousin "priority sort" where you create threads where you set the priority of each to be related to the value 'n' of the element, and all fractionally lower than the parent thread (most UNIXes are not that flexible but some realtime OSes are) then as the last step you 'yield' and the threads print out their contents in priority order and poof they are sorted. But again, the sorting happened in the kernel when they got inserted into the runq in priority order.
Sleep Sort 不违反排序理论；它利用非比较机制，而复杂度分析还依赖架构和比较成本假设。
先100%说清楚，以免刚入门的人误以为这颠覆了数学。这是个有趣但完全正常的结果。首先，线性时间排序算法有不少，基数排序、鸽巢排序和计数排序都是；O(n log n) 只适用于基于比较的排序。其次，评论里很多人在担心调度器、sleep 的非确定性以及这是否真的意味着线性时间，我觉得不值得纠结，因为我们已经有了线性时间排序算法。第三，这些排序界都假设冯·诺依曼架构，尤其是常数时间内存和常数时间比较；比较非常大的数时，这些界会变差。
antics查看英文原文
Just to be 100% clear, in case anyone who is new to the field stumbles on this thread, this is NOT breaking math or anything. This is a fun, but totally normal result. First of all, there are quite a few linear time sorting algorithms. Radix, pigeonhole, and counting sort are all linear time sorting algorithms. The popular result that any comparison-based sorting algorithm works in O(n log n) applies _specifically_ to comparison-based sorting algorithms, and not those like the above. So, even if you ignore the underlying mechanics of the OS scheduler and assume sleep works "perfectly", the result would not that unusual. Second off, in the comments there appears to be considerable time worrying about the technicalities of the scheduler, the nondeterministic nature of sleep, and so on, and whether this really implies linear time bound. IMHO these are not worth worrying about because we already have linear time sorting algorithms. It's fine to assume the scheduler adds no significant asymptotic cost here, even if we know differently. Third off, remember that all of these sorting bounds assume machines of the Von Neumann architecture. In particular, this model assumes constant time memory and constant time comparison operations. In cases where you're comparing really big numbers, these bounds get worse. This is easy to forget, but worth remembering just since we're on the subject anyway.
实际排序成本落在内核定时器的红黑树上，因此复杂度为 O(n log n)。
应该知道，最终是内核的定时器调度器在做排序。在 Linux 中这大概是红黑树，所以 sleep sort（在它能正常工作时）的性能是 O(n log n)。
ambrop7查看英文原文
One should know that it is the timer scheduler of the kernel which ends up doing the sorting. With Linux, this is probably a red-black tree[1], so performance of sleep sort (when it works) is O(n *log(n)). [1] https://www.kernel.org/doc/Documentation/timers/hrtimers.txt
帖子里有 OpenMP C、Perl 6 等简洁实现，顺带让人学到并行编程语法。
我对使用 OpenMP 的 C 解法（#81楼）的简洁印象深刻，尤其是相比冗长得多的 Erlang 和 Haskell 例子。我一直读，心想“fork 在哪？”只看到简单的 for……然后想起 # 在 C 里是预处理指令而非注释，又谷歌了“parallel omp for”。所以我今天真从这个荒诞帖子里学到了东西：OpenMP。还有 Perl 6 的一行写法可爱得可笑，我不确定它是否真能工作，但若可以，Perl 6 的简洁程度比我以为的还高；我也了解了 Perl 6 的超运算符。简言之，配早茶读这篇太棒了。
SwellJoe查看英文原文
I was impressed by the brevity of the C solution using OpenMP (comment #81), especially compared to significantly more verbose Erlang and Haskell examples. I kept reading it, thinking, "Where's the fork?" and seeing nothing but a simple for...and then remembered that # is a preprocessor directive, rather than a comment, in C, and then googled for "parallel omp for". So, I actually learned something today from that ridiculous thread: http://en.wikipedia.org/wiki/OpenMP Also, the Perl 6 one-liner is sort of laughably cute . I'm not sure I believe it would actually work, but if it does, the conciseness of Perl 6 is even higher than I'd realized; dropping about 9 words from the Perl 5 one-liner (which is already very small). But, I learned about the hyper operators in Perl 6, which is also cool: http://perl6advent.wordpress.com/2009/12/06/day-6-going-into-hyperspace/ In short, that was awesome reading over my morning tea.
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选