今天看到这篇文章，颇为震撼，感叹算法之“神通”。借助于合适的算法可以完成看似不可能的事情。
最早这个问题是在Stack Overflow网站上面给出的(Sorting numbers in RAM)：
题目：
提供一个1M的ROM和1M的RAM，一个输入流和一个输出流。程序代码最终烧录在1M的ROM中，程序可以使用1M的RAM进行运算。输入流中依次输入100万个8位的整数，要求输出流中输出这100万个数排序后的结果。
已经可以搜索到很多解法了，今天看到一个国外的程序员的分析，觉得很有趣，想把他的分析过程简单转在这里。简单一看，根本不可能，100万个8位数无论如何也不能在1M的内存里装下。排序过程是利用归并排序，效率较高。最难的地方是在如何将排序后的100万个数字存下来。换一种思路，不一定要存下每一个数字本身，因为数字都已经排序了，那么相邻两个数字之间的差值是非常小的，如果在极端的情况下，两个数字之间的差值非常大，那么必然会有更多量的相邻数字之间的差值更小，因此存下所有的100万个数字的差值需要的空间是可以估算的。平均每一个差值的大小为：10^8/100万 = 100，100需要7个bit位来表示，因此共需要100万×7 = 875, 000 字节，不到1M的空间。接下来的问题是如何编码这100万个差值，能尽可能压缩空间，作者举出了算数编码来解决这一问题，最终给出所需要的内存为小于1070312.5bytes。另外还给出了一个针对该问题的哈夫曼编码解决。算数编码看懂了，但是怎样运用到解决本问题中，还不是太明白。同时作者也给出了339行的解决问题的实战代码。
另外文中也提到了另外一位程序员使用其他办法解决了该问题：Nick Cleaton。