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

如果数字的范围是有限的(只能有2个8位数，或者只有10个不同的8位数)，那么你可以编写一个优化的排序算法。但如果你想对所有可能的8位数进行排序，这在内存那么少的情况下是不可能的。

你用的是哪种电脑?它可能没有任何其他“正常”的本地存储，但它是否有视频RAM，例如?100万像素x每像素32位(比如说)非常接近你所需的数据输入大小。

(我主要是问旧的Acorn RISC PC的内存，如果你选择低分辨率或低颜色深度的屏幕模式，它可以“借用”VRAM来扩展可用的系统RAM !)这在只有几MB普通RAM的机器上非常有用。

我们有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”分隔，然后我认为我们可以保持足够短的差距表示，但它需要更多的分析。

现在的目标是一个实际的解决方案，覆盖所有可能的情况下，输入在8位数范围内，只有1MB的RAM。注:工作正在进行中，明天继续。使用对已排序整型的增量进行算术编码，对于1M个已排序整型，最坏的情况是每个条目花费大约7位(因为99999999/1000000是99，而log2(99)几乎是7位)。

但是你需要将1m个整数排序到7位或8位!级数越短，delta就越大，因此每个元素的比特数就越多。

我正在努力尽可能多地压缩(几乎)在原地。第一批接近250K的整数最多每个需要大约9位。因此结果大约需要275KB。重复使用剩余的空闲内存几次。然后解压缩-就地合并-压缩这些压缩块。这很难，但也是可能的。我认为。

合并后的列表将越来越接近每整数7位的目标。但是我不知道合并循环需要多少次迭代。也许3。

但是算术编码实现的不精确性可能使它不可能实现。如果这个问题是可能的，它将是非常紧张的。

有志愿者吗?

假设这个任务是可能的。在输出之前，内存中会有一个百万个排序数字的表示。有多少种不同的表示法?由于可能有重复的数字，我们不能使用nCr(选择)，但有一种叫做multichoose的操作，它适用于多集。

在0..99,999,999范围内有22e2436455种方法来选择一百万个数字。 这需要8,093,730位来表示每个可能的组合，或1,011,717字节。

所以理论上是可能的，如果你能想出一个合理(足够)的数字排序表。例如，一个疯狂的表示可能需要一个10MB的查找表或数千行代码。

但是，如果“1M RAM”意味着100万个字节，那么显然没有足够的空间。事实上，多5%的内存使它在理论上成为可能，这对我来说意味着表示必须非常有效，可能是不理智的。