由于ROM大小不计算，因此除了TCP缓冲区外，不需要任何额外的RAM。只需要实现一个大的有限状态机。每个状态表示读入的多组数字。在读取了一百万个数字之后，只需打印出与所达到的状态相对应的数字。

由于ROM大小不计算，因此除了TCP缓冲区外，不需要任何额外的RAM。只需要实现一个大的有限状态机。每个状态表示读入的多组数字。在读取了一百万个数字之后，只需打印出与所达到的状态相对应的数字。

下面是一些可以解决这个问题的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排序问题 使用定点数学的算术编码

If the numbers are evenly distributed we can use Counting sort. We should keep the number of times that each number is repeated in an array. Available space is: 1 MB - 3 KB = 1045504 B or 8364032 bits Number of bits per number= 8364032/1000000 = 8 Therefore, we can store the number of times each number is repeated to the maximum of 2^8-1=255. Using this approach we have an extra 364032 bits unused that can be used to handle cases where a number is repeated more than 255 times. For example we can say a number 255 indicates a repetition greater than or equal to 255. In this case we should store a sequence of numbers+repetitions. We can handle 7745 special cases as shown bellow:

364032/(表示每个数字所需的位数+表示100万所需的位数)= 364032 / (27+20)=7745

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

但是，不管数据是如何表示的，一旦它被排序，它就可以以前缀压缩的形式存储，其中数字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字节来存储最终结果+开销。