我们有1 MB - 3 KB RAM = 2^23 - 3*2^13位= 8388608 - 24576 = 8364032位可用。

我们给出10^8范围内的10^6个数。这给出了~100 < 2^7 = 128的平均差距

让我们首先考虑一个比较简单的问题，即当所有间距都< 128时，数字间距相当均匀。这很简单。只存储第一个数字和7位空白:

(27位)+ 10^6个7位间隔数=需要7000027位

注意重复的数字间隔为0。

但如果间隔大于127呢?

好吧，让我们直接表示小于127的间隙大小，但是127的间隙大小后面跟着一个连续的8位编码来表示实际的间隙长度:

 10xxxxxx xxxxxxxx                       = 127 .. 16,383
 110xxxxx xxxxxxxx xxxxxxxx              = 16384 .. 2,097,151

etc.

注意这个数字表示描述了它自己的长度，所以我们知道下一个间隙数何时开始。

对于小于127的小间隙，仍然需要7000027位。

可能有高达(10^8)/(2^7)= 781250个23位的间隙数，需要额外的16* 781250 = 12500,000位，这是太多了。我们需要一个更紧凑和缓慢增加的差距表示。

平均差距大小是100，所以如果我们把它们重新排序 [100, 99, 101, 98, 102，…]， 2, 198, 1, 199, 0, 200, 201, 202，…] 然后用密集的二进制斐波那契基编码索引它，没有对零(例如，11011=8+5+2+1=16)，数字用“00”分隔，然后我认为我们可以保持足够短的差距表示，但它需要更多的分析。

If it is possible to read the input file more than once (your problem statement doesn't say it can't), the following should work. It is described in Benchley's book "Programming Perls." If we store each number in 8 bytes we can store 250,000 numbers in one megabyte. Use a program that makes 40 passes over the input file. On the first pass it reads into memory any integer between 0 and 249,999, sorts the (at most) 250,000 integers and writes them to the output file. The second pass sorts the integers from 250,000 to 499,999 and so on to the 40th pass, which sorts 9,750,000 to 9,999,999.

你最多要数到99,999,999，并在沿途标明1,000,000个站点。因此，可以使用位流进行解释，即1表示递增计数器，0表示输出数字。如果流中的前8位是00110010，到目前为止我们将有0,0,2,2,3。

Log (99,999,999 + 1,000,000) / Log(2) = 26.59。你的内存中有2^28位。你只需要用一半!

基数树表示可以接近于处理这个问题，因为基数树利用了“前缀压缩”的优势。但是很难想象一个基树表表法可以在一个字节中表示单个节点——两个可能是极限。

但是，不管数据是如何表示的，一旦它被排序，它就可以以前缀压缩的形式存储，其中数字10、11和12将由001b、001b、001b表示，表示从前一个数字增加1。那么，也许10101b表示增量5,1101001b表示增量9，以此类推。

下面是这类问题的一般解决方案:

一般程序

所采取的方法如下。该算法在一个32位字的缓冲区上操作。它在循环中执行以下过程:

We start with a buffer filled with compressed data from the last iteration. The buffer looks like this |compressed sorted|empty| Calculate the maximum amount of numbers that can be stored in this buffer, both compressed and uncompressed. Split the buffer into these two sections, beginning with the space for compressed data, ending with the uncompressed data. The buffer looks like |compressed sorted|empty|empty| Fill the uncompressed section with numbers to be sorted. The buffer looks like |compressed sorted|empty|uncompressed unsorted| Sort the new numbers with an in-place sort. The buffer looks like |compressed sorted|empty|uncompressed sorted| Right-align any already compressed data from the previous iteration in the compressed section. At this point the buffer is partitioned |empty|compressed sorted|uncompressed sorted| Perform a streaming decompression-recompression on the compressed section, merging in the sorted data in the uncompressed section. The old compressed section is consumed as the new compressed section grows. The buffer looks like |compressed sorted|empty|

执行此过程，直到所有数字都已排序。

压缩

当然，这种算法只有在知道实际要压缩什么之前，才有可能计算出新排序缓冲区的最终压缩大小。其次，压缩算法需要足够好来解决实际问题。

所使用的方法使用三个步骤。首先，算法将始终存储排序序列，因此我们可以只存储连续条目之间的差异。每个差值都在[0,99999999]的范围内。

这些差异随后被编码为一元比特流。这个流中的1表示“向累加器添加1,0表示“将累加器作为一个条目发出，并重置”。所以差N由N个1和1个0表示。

所有差异的和将接近算法支持的最大值，所有差异的计数将接近算法中插入的值的数量。这意味着我们期望流在最后包含最大值1和计数0。这允许我们计算流中0和1的期望概率。即，0的概率为count/(count+maxval)， 1的概率为maxval/(count+maxval)。

我们使用这些概率来定义这个比特流上的算术编码模型。这个算术代码将在最佳空间中精确地编码1和0的数量。我们可以计算该模型对于任何中间位流所使用的空间:bits = encoded * log2(1 + amount / maxval) + maxval * log2(1 + maxval / amount)。若要计算算法所需的总空间，请将encoded设置为amount。

为了不需要大量的迭代，可以向缓冲区添加少量开销。这将确保算法将至少对适合这个开销的数量进行操作，因为到目前为止，算法最大的时间成本是每个周期的算术编码压缩和解压缩。

除此之外，在算术编码算法的定点近似中，存储簿记数据和处理轻微的不准确性是需要一些开销的，但总的来说，即使使用可以包含8000个数字的额外缓冲区，该算法也能够容纳1MiB的空间，总共1043916字节的空间。

最优

除了减少算法的开销外，理论上不可能得到更小的结果。为了仅仅包含最终结果的熵，1011717个字节是必要的。如果我们减去为提高效率而增加的额外缓冲区，该算法使用1011916字节来存储最终结果+开销。

下面是一些可以解决这个问题的c++代码。

满足内存约束的证明:

编辑:无论是在这篇文章中还是在他的博客中，都没有作者提供的最大内存要求的证据。由于编码值所需的比特数取决于先前编码的值，因此这样的证明可能不是简单的。作者指出，根据经验，他可能遇到的最大编码大小是1011732，并任意选择了1013000的缓冲区大小。

typedef unsigned int u32;

namespace WorkArea
{
    static const u32 circularSize = 253250;
    u32 circular[circularSize] = { 0 };         // consumes 1013000 bytes

    static const u32 stageSize = 8000;
    u32 stage[stageSize];                       // consumes 32000 bytes

    ...

这两个数组总共占用1045000字节的存储空间。剩下1048576 - 1045000 - 2×1024 = 1528字节作为剩余变量和堆栈空间。

它在我的至强W3520上运行大约23秒。您可以使用以下Python脚本验证程序是否工作，假设程序名称为sort1mb.exe。

from subprocess import *
import random

sequence = [random.randint(0, 99999999) for i in xrange(1000000)]

sorter = Popen('sort1mb.exe', stdin=PIPE, stdout=PIPE)
for value in sequence:
    sorter.stdin.write('%08d\n' % value)
sorter.stdin.close()

result = [int(line) for line in sorter.stdout]
print('OK!' if result == sorted(sequence) else 'Error!')

该算法的详细解释可以在以下一系列帖子中找到:

1MB排序说明 算术编码与1MB排序问题 使用定点数学的算术编码