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

解决问题的一种方法是做以下可怕的事情，任何人在任何情况下都不应该尝试:使用网络流量存储数据。不，我指的不是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).

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

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

解决问题的一种方法是做以下可怕的事情，任何人在任何情况下都不应该尝试:使用网络流量存储数据。不，我指的不是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).

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

我有一台有1M内存的电脑，没有其他本地存储

另一种作弊方法:你可以使用非本地(网络)存储代替(你的问题不排除这一点)，调用一个网络服务，它可以使用直接的基于磁盘的归并排序(或者只需要足够的RAM来在内存中排序，因为你只需要接受1M的数字)，而不需要(公认非常巧妙的)已经给出的解决方案。

这可能是作弊，但不清楚你是在寻找一个现实问题的解决方案，还是一个让人扭曲规则的谜题……如果是后者，那么简单的欺骗可能比复杂但“真实”的解决方案(正如其他人指出的那样，后者只能用于可压缩输入)得到更好的结果。

我认为解决方案是结合视频编码的技术，即离散余弦变换。在数字视频中，不是将视频的亮度或颜色的变化记录为常规值，如110 112 115 116，而是从最后一个中减去每一个(类似于运行长度编码)。110 112 115 116变成110 2 3 1。这些值，2,3 1比原始值需要更少的比特。

So lets say we create a list of the input values as they arrive on the socket. We are storing in each element, not the value, but the offset of the one before it. We sort as we go, so the offsets are only going to be positive. But the offset could be 8 decimal digits wide which this fits in 3 bytes. Each element can't be 3 bytes, so we need to pack these. We could use the top bit of each byte as a "continue bit", indicating that the next byte is part of the number and the lower 7 bits of each byte need to be combined. zero is valid for duplicates.

当列表填满时，数字之间的距离应该越来越近，这意味着平均只有1个字节用于确定到下一个值的距离。7位值和1位偏移(如果方便的话)，但可能存在一个“继续”值需要少于8位的最佳点。

总之，我做了一些实验。我使用随机数生成器，我可以将100万个排序过的8位十进制数字放入大约1279000字节。每个数字之间的平均间隔始终是99…

public class Test {
    public static void main(String[] args) throws IOException {
        // 1 million values
        int[] values = new int[1000000];

        // create random values up to 8 digits lrong
        Random random = new Random();
        for (int x=0;x<values.length;x++) {
            values[x] = random.nextInt(100000000);
        }
        Arrays.sort(values);

        ByteArrayOutputStream baos = new ByteArrayOutputStream();

        int av = 0;    
        writeCompact(baos, values[0]);     // first value
        for (int x=1;x<values.length;x++) {
            int v = values[x] - values[x-1];  // difference
            av += v;
            System.out.println(values[x] + " diff " + v);
            writeCompact(baos, v);
        }

        System.out.println("Average offset " + (av/values.length));
        System.out.println("Fits in " + baos.toByteArray().length);
    }

    public static void writeCompact(OutputStream os, long value) throws IOException {
        do {
            int b = (int) value & 0x7f;
            value = (value & 0x7fffffffffffffffl) >> 7;
            os.write(value == 0 ? b : (b | 0x80));
        } while (value != 0);
    }
}

我在这里的建议很大程度上归功于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位增量的桶

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