仅由于 1 兆字节和 100 万字节之间的差异，才有可能解决。大约有 2 次方 8093729.5 种不同的方法来选择 100 万个 8
位数字，允许重复且顺序不重要，因此只有 100 万字节 RAM 的机器没有足够的状态来表示所有可能性。但是 1M（TCP/IP 少 2k）是
102210248 = 8372224 位，所以有一个解决方案是可能的。

第 1 部分，初始解决方案

这种方法需要1M多一点，稍后我会对其进行细化以适应1M。

我会将 0 到 99999999 范围内的数字的紧凑排序列表存储为 7 位数字的子列表序列。第一个子列表包含从 0 到 127 的数字，第二个子列表包含从
128 到 255 的数字等。100000000/128 正好是 781250，因此需要 781250 个这样的子列表。

每个子列表包含一个 2 位的子列表标头，后跟一个子列表主体。子列表主体占用每个子列表条目 7
位。子列表都连接在一起，并且该格式可以区分一个子列表的结束位置和下一个子列表的开始位置。完全填充的列表所需的总存储空间为 2781250 +
71000000 = 8562500 位，约为 1.021 M 字节。

4 个可能的子列表标头值是：

00 空子列表，没有后续内容。

01 Singleton，子列表中只有一个条目，接下来的 7 位保存它。

10 子列表至少包含 2 个不同的数字。条目以非递减顺序存储，除了最后一个条目小于或等于第一个条目。这允许识别子列表的结尾。例如，数字 2,4,6
将存储为 (4,6,2)。数字 2,2,3,4,4 将存储为 (2,3,4,4,2)。

11 子列表包含 2 个或多个重复的单个数字。接下来的 7 位给出数字。然后是零个或多个值为 1 的 7 位条目，然后是一个值为 0 的 7
位条目。子列表主体的长度决定了重复的次数。例如，数字 12,12 将存储为 (12,0)，数字 12,12,12 将存储为
(12,1,0)，12,12,12,12 将存储为 (12,1 ,1,0) 等等。

我从一个空列表开始，读取一堆数字并将它们存储为 32
位整数，对新数字进行适当的排序（可能使用堆排序），然后将它们合并到一个新的紧凑排序列表中。重复直到没有更多的数字要读取，然后再次遍历紧凑列表以生成输出。

下面的行表示列表合并操作开始之前的内存。“O”是保存已排序 32
位整数的区域。“X”是保存旧紧凑列表的区域。“=”符号是紧凑列表的扩展空间，“O”中的每个整数都有 7 位。“Z”是其他随机开销。

ZZZOOOOOOOOOOOOOOOOOOOOOOOOOO==========XXXXXXXXXXXXXXXXXXXXXXXXXX

合并例程从最左边的“O”和最左边的“X”开始读取，并从最左边的“=”开始写入。在所有新整数合并之前，写指针不会捕获紧凑列表读取指针，因为两个指针都为每个子列表提前
2 位，为旧紧凑列表中的每个条目提前 7 位，并且有足够的额外空间新数字的 7 位条目。

第 2 部分，把它塞进 1M

要将上面的解决方案压缩为 1M，我需要使紧凑列表格式更加紧凑。我将去掉其中一种子列表类型，这样就只有 3
个不同的可能的子列表标题值。然后我可以使用“00”、“01”和“1”作为子列表标题值并节省一些位。子列表类型是：

一个空子列表，没有任何后续。

B Singleton，子列表中只有一个条目，接下来的 7 位保存它。

C 子列表至少包含 2 个不同的数字。条目以非递减顺序存储，除了最后一个条目小于或等于第一个条目。这允许识别子列表的结尾。例如，数字 2,4,6 将存储为
(4,6,2)。数字 2,2,3,4,4 将存储为 (2,3,4,4,2)。

D 子列表由单个数字的 2 次或更多次重复组成。

我的 3 个子列表标题值将是“A”、“B”和“C”，所以我需要一种表示 D 类型子列表的方法。

假设我有 C 类型的子列表标头，后跟 3 个条目，例如“C[17][101][58]”。如上所述，这不能是有效 C
类型子列表的一部分，因为第三个条目小于第二个但大于第一个。我可以使用这种类型的构造来表示 D
类型的子列表。就位而言，我有“C{00?????}{1??????}{01?????}”的任何地方都是不可能的 C 类型子列表。我将使用它来表示由单个数字的
3 次或更多次重复组成的子列表。前两个 7 位字对数字（下面的“N”位）进行编码，后跟零个或多个 {0100001} 字，后跟一个 {0100000} 字。

For example, 3 repetitions: "C{00NNNNN}{1NN0000}{0100000}", 4 repetitions: "C{00NNNNN}{1NN0000}{0100001}{0100000}", and so on.

这只剩下的列表恰好包含一个数字的 2 次重复。我将用另一个不可能的 C
类型子列表模式表示那些：“C{0??????}{11?????}{10?????}”。前 2 个单词中的 7
位数字有足够的空间，但是这种模式比它所代表的子列表长，这使事情变得更复杂一些。最后的五个问号可以认为不是模式的一部分，所以我有：“C{0NNNNNN}{11N????}10”作为我的模式，要重复的数字存储在“N
“s。这2位太长了。

我将不得不借用 2 位并从该模式中的 4
个未使用的位中偿还它们。读取时，遇到“C{0NNNNNN}{11N00AB}10”，输出“N”中数字的2个实例，用位A和B覆盖末尾的“10”，并将读取指针倒回2位。该算法可以进行破坏性读取，因为每个紧凑列表仅遍历一次。

当写入单个数字的 2 次重复的子列表时，写入“C{0NNNNNN}11N00”并将借用位计数器设置为
2。每次写入时借用位计数器非零，每写入一个位，它就会递减，并且当计数器达到零时写入“10”。所以接下来写入的 2 位将进入插槽 A 和
B，然后“10”将被丢弃到末尾。

使用“00”、“01”和“1”表示的 3
个子列表标题值，我可以将“1”分配给最流行的子列表类型。我需要一个小表来将子列表标题值映射到子列表类型，并且我需要每个子列表类型的出现计数器，以便我知道最好的子列表标题映射是什么。

当所有子列表类型都同样流行时，会出现完全填充的紧凑列表的最坏情况最小表示。在这种情况下，我为每 3 个子列表标头保存 1 位，因此列表大小为
2781250 + 71000000 - 781250/3 = 8302083.3 位。向上舍入到 32 位字边界，即 8302112 位或
1037764 字节。

1M 减去 TCP/IP 状态和缓冲区的 2k 为 1022*1024 = 1046528 字节，剩下 8764 字节可玩。

但是更改子列表标头映射的过程呢？在下面的内存映射中，“Z”是随机开销，“=”是空闲空间，“X”是紧凑列表。

ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

从最左边的“X”开始阅读，从最左边的“=”开始写作，然后向右工作。完成后，紧凑列表会更短一些，并且会位于错误的内存末尾：

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

那么我需要把它分流到右边：

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

在标头映射更改过程中，多达 1/3 的子列表标头将从 1 位更改为 2 位。在最坏的情况下，这些都将排在列表的首位，因此在开始之前我至少需要
781250/3 位的空闲存储空间，这让我回到了紧凑列表之前版本的内存需求： (

为了解决这个问题，我将 781250 个子列表分成 10 个子列表组，每个组有 78125 个子列表。每个组都有自己独立的子列表标头映射。使用字母 A 到
J 表示组：

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

在子列表标头映射更改期间，每个子列表组都会缩小或保持不变：

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAA=====BBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABB=====CCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCC======DDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDD======EEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEE======FFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFF======GGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGG=======HHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHH=======IJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHI=======JJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ=======
ZZZ=======AAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

在映射更改期间子列表组的最坏情况临时扩展是 78125/3 = 26042 位，低于 4k。如果我允许 4k 加上 1037764
字节用于完全填充的紧凑列表，那么内存映射中的“Z”将剩下 8764 - 4096 = 4668 字节。

对于 10 个子列表标头映射表、30
个子列表标头出现计数以及我需要的其他几个计数器、指针和小缓冲区，以及我在没有注意到的情况下使用的空间，比如用于函数调用返回地址的堆栈空间和局部变量。

第 3 部分，运行需要多长时间？

对于空的紧凑列表，1 位列表头将用于空子列表，列表的起始大小将为 781250 位。在最坏的情况下，每个添加的数字列表都会增长 8 位，因此每个 32
位数字需要 32 + 8 = 40 位的可用空间才能放置在列表缓冲区的顶部，然后进行排序和合并。在最坏的情况下，更改子列表标头映射会导致 2781250
+ 7entries - 781250/3 位的空间使用。

如果列表中至少有 800000 个数字，则在每第五次合并后更改子列表标头映射的策略，最坏的情况运行将涉及总共约 30M 的紧凑列表读取和写入活动。

资源：

http://nick.cleaton.net/ramsortsol.html