今天看到这篇文章，颇为震撼，感叹算法之“神通”。借助于合适的算法可以完成看似不可能的事情。

   最早这个问题是在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行的解决问题的实战代码。

   系列博客链接：1 2 3 4

   另外文中也提到了另外一位程序员使用其他办法解决了该问题：Nick Cleaton。

建议继续学习：

1. 快速排序（Quicksort）的Javascript实现    (阅读：10090)
2. 腾讯-1亿个数据取前1万大的整数-题解答    (阅读：9042)
3. 深入浅出插入类排序算法(直接插入, 折半插入, 希尔排序)    (阅读：6188)
4. 深入浅出交换类排序算法(冒泡排序,快速排序)    (阅读：5986)
5. Java程序员必知的8大排序算法    (阅读：4458)
6. Mysql中的排序优化    (阅读：4359)
7. Vim(gVim)对排序的妙用    (阅读：4221)
8. 快速排序详细分析    (阅读：3955)
9. 深入浅出选择类排序算法(简单选择排序,堆排序)    (阅读：3753)
10. 排序算法 Sleep Sort    (阅读：3157)