To represent the sorted array one can just store the first element and the difference between adjacent elements. In this way we are concerned with encoding 10^6 elements that can sum up to at most 10^8. Let's call this D. To encode the elements of D one can use a Huffman code. The dictionary for the Huffman code can be created on the go and the array updated every time a new item is inserted in the sorted array (insertion sort). Note that when the dictionary changes because of a new item the whole array should be updated to match the new encoding.

如果每个唯一元素的数量相等，则编码D中每个元素的平均比特数将最大化。比如元素d1 d2…， dN在D中各出现F次。在这种情况下(最坏的情况是输入序列中同时有0和10^8)我们有

sum（1<=i<=N） F. di = 10^8

在哪里

sum(1<=i<=N) F=10^6，或F=10^6/N，归一化频率将是p= F/10^=1/N

平均比特数为-log2(1/P) = log2(N)。在这种情况下，我们应该找到使n最大化的情况，这发生在di从0开始的连续数，或者di= i-1时

10 ^ 8 =(1 < =我< = N) f . di =(1 < =我< = N) (10 ^ 6 / N)(张)= (10 ^ 6 / N) N (N - 1) / 2

i.e.

N <= 201。在这种情况下，平均比特数是log2(201)=7.6511，这意味着我们将需要大约1字节的每个输入元素来保存排序的数组。注意，这并不意味着D一般不能有超过201个元素。它只是说明，如果D的元素是均匀分布的，那么D的唯一值不可能超过201个。

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

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

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

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

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

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

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

我们可以利用网络堆栈，在我们得到所有数字之前，按顺序发送数字。如果你发送1M的数据，TCP/IP会把它分解成1500字节的数据包，并按照目标发送。每个包将被赋予一个序列号。

我们可以用手来做。在填满内存之前，我们可以对现有的数据进行排序，并将列表发送给目标，但在每个数字周围的序列中留下空洞。然后用同样的方法处理第二个1/2的数字，使用序列中的这些洞。

远端的网络堆栈将按顺序组装结果数据流，然后将其提交给应用程序。

它使用网络来执行归并排序。这是一个完全的黑客，但我是受到之前列出的其他网络黑客的启发。

To represent the sorted array one can just store the first element and the difference between adjacent elements. In this way we are concerned with encoding 10^6 elements that can sum up to at most 10^8. Let's call this D. To encode the elements of D one can use a Huffman code. The dictionary for the Huffman code can be created on the go and the array updated every time a new item is inserted in the sorted array (insertion sort). Note that when the dictionary changes because of a new item the whole array should be updated to match the new encoding.

如果每个唯一元素的数量相等，则编码D中每个元素的平均比特数将最大化。比如元素d1 d2…， dN在D中各出现F次。在这种情况下(最坏的情况是输入序列中同时有0和10^8)我们有

sum（1<=i<=N） F. di = 10^8

在哪里

sum(1<=i<=N) F=10^6，或F=10^6/N，归一化频率将是p= F/10^=1/N

平均比特数为-log2(1/P) = log2(N)。在这种情况下，我们应该找到使n最大化的情况，这发生在di从0开始的连续数，或者di= i-1时

10 ^ 8 =(1 < =我< = N) f . di =(1 < =我< = N) (10 ^ 6 / N)(张)= (10 ^ 6 / N) N (N - 1) / 2

i.e.

N <= 201。在这种情况下，平均比特数是log2(201)=7.6511，这意味着我们将需要大约1字节的每个输入元素来保存排序的数组。注意，这并不意味着D一般不能有超过201个元素。它只是说明，如果D的元素是均匀分布的，那么D的唯一值不可能超过201个。

我认为解决方案是结合视频编码的技术，即离散余弦变换。在数字视频中，不是将视频的亮度或颜色的变化记录为常规值，如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);
    }
}