你最多要数到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位。你只需要用一半!

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

我在这里的建议很大程度上归功于Dan的解决方案

首先，我假设解决方案必须处理所有可能的输入列表。我认为流行的答案并没有做出这样的假设(在我看来这是一个巨大的错误)。

众所周知，任何形式的无损压缩都不会减小所有输入的大小。

所有流行的答案都假设它们能够有效地应用压缩来允许它们有额外的空间。事实上，一个足够大的额外空间块，以未压缩的形式保存他们部分完成的列表的一部分，并允许他们执行排序操作。这只是一个糟糕的假设。

对于这样的解决方案，任何了解如何进行压缩的人都能够设计一些不能很好地压缩该方案的输入数据，并且“解决方案”很可能会由于空间不足而崩溃。

相反，我采用数学方法。我们可能的输出是所有长度为LEN的列表，由0..MAX范围内的元素组成。这里LEN是1,000,000,MAX是100,000,000。

对于任意的LEN和MAX，编码此状态所需的比特数为:

Log2(MAX multichoice LEN)

因此，对于我们的数字，一旦我们完成了接收和排序，我们将需要至少Log2(100,000,000 MC 1,000,000)位来存储我们的结果，以一种能够唯一区分所有可能输出的方式。

这是~= 988kb。所以我们有足够的空间来存放结果。从这个角度来看，这是可能的。

[删除了无意义的漫谈，现在有更好的例子…]

最好的答案在这里。

另一个很好的答案是这里，它基本上使用插入排序作为函数，将列表扩展为一个元素(缓冲一些元素并进行预先排序，以允许一次插入多个元素，节省一些时间)。使用一个很好的压缩状态编码，7位增量的桶

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

我认为从组合学的角度来思考这个问题:有多少种可能的排序数字的组合?如果我们给出的组合是0,0,0 ....，0代码0，和0,0,0，…，1代码1，和999999999,99999999，…99999999是代码N, N是什么?换句话说，结果空间有多大?

Well, one way to think about this is noticing that this is a bijection of the problem of finding the number of monotonic paths in an N x M grid, where N = 1,000,000 and M = 100,000,000. In other words, if you have a grid that is 1,000,000 wide and 100,000,000 tall, how many shortest paths from the bottom left to the top right are there? Shortest paths of course require you only ever either move right or up (if you were to move down or left you would be undoing previously accomplished progress). To see how this is a bijection of our number sorting problem, observe the following:

您可以将路径中的任何水平支腿想象成排序中的一个数字，其中支腿的Y位置表示值。

所以如果路径只是向右移动一直到最后，然后一直跳到顶部，这相当于顺序为0,0,0，…，0。相反，如果它开始时一直跳到顶部，然后向右移动1,000,000次，这相当于999999999,99999999，……, 99999999。它向右移动一次，然后向上移动一次，然后向右移动一次，然后向上移动一次，等等，直到最后(然后必然会一直跳到顶部)，相当于0,1,2,3，…，999999。

幸运的是，这个问题已经解决了，这样的网格有(N + M)个选择(M)条路径:

(1,000,000 + 100,000,000)选择(100,000,000)~= 2.27 * 10^2436455

N因此等于2.27 * 10^2436455，因此代码0表示0,0,0，…，0和代码2.27 * 10^2436455，一些变化表示999999999,99999999，…, 99999999。

为了存储从0到2.27 * 10^2436455的所有数字，您需要lg2(2.27 * 10^2436455) = 8.0937 * 10^6位。

1兆字节= 8388608比特> 8093700比特

这样看来，我们至少有足够的空间来存储结果!当然，有趣的部分是在数字流进来时进行排序。不确定最好的方法是我们有294908位剩余。我想一个有趣的技巧是在每个点都假设这是整个排序，找到该排序的代码，然后当你收到一个新数字时，返回并更新之前的代码。手，手，手。

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

第一部分，初始解

这个方法需要1M多一点，我稍后会改进它以适应1M。

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

每个子列表由一个2位的子列表头和一个子列表体组成。子列表主体为每个子列表条目占用7位。所有子列表都连接在一起，并且这种格式可以确定一个子列表的结束位置和下一个子列表的开始位置。一个完全填充的列表所需的总存储空间是2*781250 + 7*1000000 = 8562500位，大约是1.021 m -字节。

4个可能的子列表头值是:

00空子列表，后面什么都没有。

01单例，在子列表中只有一个条目，并且接下来的7位保存它。

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

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

我从一个空列表开始，读入一堆数字并将它们存储为32位整数，对新数字进行排序(可能使用heapsort)，然后将它们合并到一个新的紧凑排序列表中。重复该操作，直到不再需要读取数字为止，然后再次遍历紧凑列表以生成输出。

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

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

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

第二部分，把它塞进1M

为了将上面的解决方案压缩到1M，我需要使紧凑列表的格式更紧凑一点。我将去掉其中一个子列表类型，这样就只有3个不同的子列表头值。然后我可以使用“00”，“01”和“1”作为子列表头值，并节省一些比特。子列表类型为:

空子列表，后面什么都没有。

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

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

子列表由单个数字的2个或2个以上的重复组成。

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

Suppose I have the C-type sublist header followed by 3 entries, such as "C[17][101][58]". This can't be part of a valid C-type sublist as described above, since the third entry is less than the second but more than the first. I can use this type of construct to represent a D-type sublist. In bit terms, anywhere I have "C{00?????}{1??????}{01?????}" is an impossible C-type sublist. I'll use this to represent a sublist consisting of 3 or more repetitions of a single number. The first two 7-bit words encode the number (the "N" bits below) and are followed by zero or more {0100001} words followed by a {0100000} word.

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

That just leaves lists that hold exactly 2 repetitions of a single number. I'll represent those with another impossible C-type sublist pattern: "C{0??????}{11?????}{10?????}". There's plenty of room for the 7 bits of the number in the first 2 words, but this pattern is longer than the sublist that it represents, which makes things a bit more complex. The five question-marks at the end can be considered not part of the pattern, so I have: "C{0NNNNNN}{11N????}10" as my pattern, with the number to be repeated stored in the "N"s. That's 2 bits too long.

我将不得不借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位，因此列表大小为2*781250 + 7*1000000 - 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个子列表头出现计数和我需要的其他几个计数器、指针和小缓冲区，以及我已经不注意使用的空间，比如函数调用返回地址和局部变量的堆栈空间，这些应该足够了。

第三部分，运行需要多长时间?

对于空的紧凑列表，1位的列表头将用于空的子列表，列表的起始大小将是781250位。在最坏的情况下，每增加一个数字，列表就增长8位，因此32 + 8 = 40位的空闲空间需要将每个32位数字放在列表缓冲区的顶部，然后排序和合并。在最坏的情况下，更改子列表报头映射将导致占用2*781250 + 7*entries - 781250/3位的空间。

如果策略是在列表中至少有800000个数字的情况下，每5次合并后更改子列表头映射，那么最坏的情况下运行将涉及大约30M的紧凑列表读写活动。

来源:

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