排序在这里是次要问题。正如其他人所说，仅仅存储整数是困难的，并且不能在所有输入上工作，因为每个数字需要27位。

我对此的看法是:只存储连续(排序)整数之间的差异，因为它们很可能很小。然后使用压缩方案，例如，每个输入数字增加2位，来编码数字存储在多少位上。 喜欢的东西:

00 -> 5 bits
01 -> 11 bits
10 -> 19 bits
11 -> 27 bits

在给定的内存限制内，应该能够存储相当数量的可能输入列表。如何选择压缩方案以使其在最大输入数量上工作的数学超出了我的范围。

我希望您能够利用输入的领域特定知识，在此基础上找到足够好的整数压缩方案。

哦，然后，当你收到数据时，你对那个排序的列表进行插入排序。

你试过转换成十六进制吗?

我可以看到前后文件大小都有了很大的减小;然后，用自由空间分步计算。也许，再次转换为dec, order，十六进制，另一个块，转换为dec, order…

对不起. .我不知道是否可行

# for i in {1..10000};do echo $(od -N1 -An -i /dev/urandom) ; done > 10000numbers
# for i in $(cat 10000numbers ); do printf '%x\n' $i; done > 10000numbers_hex
# ls -lah total 100K
drwxr-xr-x  2 diego diego 4,0K oct 22 22:32 .
drwx------ 39 diego diego  12K oct 22 22:31 ..
-rw-r--r--  1 diego diego  29K oct 22 22:33 10000numbers_hex
-rw-r--r--  1 diego diego  35K oct 22 22:31 10000numbers

在接收流时执行这些步骤。

首先设置一些合理的块大小

伪代码思想:

The first step would be to find all the duplicates and stick them in a dictionary with its count and remove them. The third step would be to place number that exist in sequence of their algorithmic steps and place them in counters special dictionaries with the first number and their step like n, n+1..., n+2, 2n, 2n+1, 2n+2... Begin to compress in chunks some reasonable ranges of number like every 1000 or ever 10000 the remaining numbers that appear less often to repeat. Uncompress that range if a number is found and add it to the range and leave it uncompressed for a while longer. Otherwise just add that number to a byte[chunkSize]

在接收流时继续执行前4步。最后一步是，如果超出内存，则失败，或者在收集完所有数据后开始输出结果，即开始对范围进行排序，并按顺序输出结果，然后按需要解压缩的顺序解压结果，并在得到它们时对它们进行排序。

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

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

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

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

到目前为止，这里还没有提到一个相当狡猾的技巧。我们假设您没有额外的方法来存储数据，但严格来说这并不正确。

解决问题的一种方法是做以下可怕的事情，任何人在任何情况下都不应该尝试:使用网络流量存储数据。不，我指的不是NAS。

你可以用以下方法对只有几个字节内存的数字进行排序:

首先取两个变量:COUNTER和VALUE。 首先将所有寄存器设置为0; 每次你收到一个整数I，增加COUNTER并将VALUE设置为max(VALUE, I); 然后向路由器发送数据集为I的ICMP echo请求报文。擦掉I，重复。 每次收到返回的ICMP包时，只需提取整数并在另一个回显请求中再次发送出去。这将产生大量的ICMP请求，其中包含整数。

Once COUNTER reaches 1000000, you have all of the values stored in the incessant stream of ICMP requests, and VALUE now contains the maximum integer. Pick some threshold T >> 1000000. Set COUNTER to zero. Every time you receive an ICMP packet, increment COUNTER and send the contained integer I back out in another echo request, unless I=VALUE, in which case transmit it to the destination for the sorted integers. Once COUNTER=T, decrement VALUE by 1, reset COUNTER to zero and repeat. Once VALUE reaches zero you should have transmitted all integers in order from largest to smallest to the destination, and have only used about 47 bits of RAM for the two persistent variables (and whatever small amount you need for the temporary values).

我知道这很可怕，我知道可能会有各种各样的实际问题，但我想这可能会让你们中的一些人发笑，或者至少会吓到你们。

Gilmanov的答案在假设上是非常错误的。它开始基于毫无意义的一百万个连续整数进行推测。这意味着没有差距。这些随机的间隙，不管有多小，真的是一个糟糕的主意。

你自己试试。获得100万个27位随机整数，对它们排序，用7-Zip, xz压缩，任何你想要的LZMA。结果超过1.5 MB。上面的前提是连续数字的压缩。即使是增量编码也超过1.1 MB。没关系，这使用了超过100 MB的RAM进行压缩。因此，即使压缩的整数也不适合这个问题，更不用说运行时RAM的使用了。

让我难过的是，人们竟然投票支持漂亮的图像和合理化。

#include <stdint.h>
#include <stdlib.h>
#include <time.h>

int32_t ints[1000000]; // Random 27-bit integers

int cmpi32(const void *a, const void *b) {
    return ( *(int32_t *)a - *(int32_t *)b );
}

int main() {
    int32_t *pi = ints; // Pointer to input ints (REPLACE W/ read from net)

    // Fill pseudo-random integers of 27 bits
    srand(time(NULL));
    for (int i = 0; i < 1000000; i++)
        ints[i] = rand() & ((1<<27) - 1); // Random 32 bits masked to 27 bits

    qsort(ints, 1000000, sizeof (ints[0]), cmpi32); // Sort 1000000 int32s

    // Now delta encode, optional, store differences to previous int
    for (int i = 1, prev = ints[0]; i < 1000000; i++) {
        ints[i] -= prev;
        prev    += ints[i];
    }

    FILE *f = fopen("ints.bin", "w");
    fwrite(ints, 4, 1000000, f);
    fclose(f);
    exit(0);

}

现在用LZMA压缩ints.bin…

    $ xz -f --keep ints.bin       # 100 MB RAM
    $ 7z a ints.bin.7z ints.bin   # 130 MB RAM
    $ ls -lh ints.bin*
        3.8M ints.bin
        1.1M ints.bin.7z
        1.2M ints.bin.xz