我认为从组合学的角度来思考这个问题:有多少种可能的排序数字的组合?如果我们给出的组合是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位剩余。我想一个有趣的技巧是在每个点都假设这是整个排序，找到该排序的代码，然后当你收到一个新数字时，返回并更新之前的代码。手，手，手。

请参阅第一个正确答案或后面带有算术编码的答案。下面你可能会发现一些有趣的，但不是100%防弹的解决方案。

这是一个非常有趣的任务，这里有另一个解决方案。我希望有人会觉得这个结果有用(或者至少有趣)。

阶段1:初始数据结构，粗略压缩方法，基本结果

Let's do some simple math: we have 1M (1048576 bytes) of RAM initially available to store 10^6 8 digit decimal numbers. [0;99999999]. So to store one number 27 bits are needed (taking the assumption that unsigned numbers will be used). Thus, to store a raw stream ~3.5M of RAM will be needed. Somebody already said it doesn't seem to be feasible, but I would say the task can be solved if the input is "good enough". Basically, the idea is to compress the input data with compression factor 0.29 or higher and do sorting in a proper manner.

让我们先解决压缩问题。有一些相关的测试已经可用:

http://www.theeggeadventure.com/wikimedia/index.php/Java_Data_Compression

“我运行了一个测试，压缩100万个连续整数使用 各种形式的压缩。结果如下:

None     4000027
Deflate  2006803
Filtered 1391833
BZip2    427067
Lzma     255040

看起来LZMA (Lempel-Ziv-Markov链算法)是一个很好的选择。我准备了一个简单的PoC，但仍有一些细节需要强调:

Memory is limited so the idea is to presort numbers and use compressed buckets (dynamic size) as temporary storage It is easier to achieve a better compression factor with presorted data, so there is a static buffer for each bucket (numbers from the buffer are to be sorted before LZMA) Each bucket holds a specific range, so the final sort can be done for each bucket separately Bucket's size can be properly set, so there will be enough memory to decompress stored data and do the final sort for each bucket separately

请注意，所附的代码是一个POC，它不能用作最终解决方案，它只是演示了使用几个较小的缓冲区以某种最佳方式(可能是压缩)存储预排序数字的想法。LZMA并不是最终的解决方案。它被用作向这个PoC引入压缩的最快方法。

请看下面的PoC代码(请注意它只是一个演示，要编译它将需要LZMA-Java):

public class MemorySortDemo {

static final int NUM_COUNT = 1000000;
static final int NUM_MAX   = 100000000;

static final int BUCKETS      = 5;
static final int DICT_SIZE    = 16 * 1024; // LZMA dictionary size
static final int BUCKET_SIZE  = 1024;
static final int BUFFER_SIZE  = 10 * 1024;
static final int BUCKET_RANGE = NUM_MAX / BUCKETS;

static class Producer {
    private Random random = new Random();
    public int produce() { return random.nextInt(NUM_MAX); }
}

static class Bucket {
    public int size, pointer;
    public int[] buffer = new int[BUFFER_SIZE];

    public ByteArrayOutputStream tempOut = new ByteArrayOutputStream();
    public DataOutputStream tempDataOut = new DataOutputStream(tempOut);
    public ByteArrayOutputStream compressedOut = new ByteArrayOutputStream();

    public void submitBuffer() throws IOException {
        Arrays.sort(buffer, 0, pointer);

        for (int j = 0; j < pointer; j++) {
            tempDataOut.writeInt(buffer[j]);
            size++;
        }            
        pointer = 0;
    }

    public void write(int value) throws IOException {
        if (isBufferFull()) {
            submitBuffer();
        }
        buffer[pointer++] = value;
    }

    public boolean isBufferFull() {
        return pointer == BUFFER_SIZE;
    }

    public byte[] compressData() throws IOException {
        tempDataOut.close();
        return compress(tempOut.toByteArray());
    }        

    private byte[] compress(byte[] input) throws IOException {
        final BufferedInputStream in = new BufferedInputStream(new ByteArrayInputStream(input));
        final DataOutputStream out = new DataOutputStream(new BufferedOutputStream(compressedOut));

        final Encoder encoder = new Encoder();
        encoder.setEndMarkerMode(true);
        encoder.setNumFastBytes(0x20);
        encoder.setDictionarySize(DICT_SIZE);
        encoder.setMatchFinder(Encoder.EMatchFinderTypeBT4);

        ByteArrayOutputStream encoderPrperties = new ByteArrayOutputStream();
        encoder.writeCoderProperties(encoderPrperties);
        encoderPrperties.flush();
        encoderPrperties.close();

        encoder.code(in, out, -1, -1, null);
        out.flush();
        out.close();
        in.close();

        return encoderPrperties.toByteArray();
    }

    public int[] decompress(byte[] properties) throws IOException {
        InputStream in = new ByteArrayInputStream(compressedOut.toByteArray());
        ByteArrayOutputStream data = new ByteArrayOutputStream(10 * 1024);
        BufferedOutputStream out = new BufferedOutputStream(data);

        Decoder decoder = new Decoder();
        decoder.setDecoderProperties(properties);
        decoder.code(in, out, 4 * size);

        out.flush();
        out.close();
        in.close();

        DataInputStream input = new DataInputStream(new ByteArrayInputStream(data.toByteArray()));
        int[] array = new int[size];
        for (int k = 0; k < size; k++) {
            array[k] = input.readInt();
        }

        return array;
    }
}

static class Sorter {
    private Bucket[] bucket = new Bucket[BUCKETS];

    public void doSort(Producer p, Consumer c) throws IOException {

        for (int i = 0; i < bucket.length; i++) {  // allocate buckets
            bucket[i] = new Bucket();
        }

        for(int i=0; i< NUM_COUNT; i++) {         // produce some data
            int value = p.produce();
            int bucketId = value/BUCKET_RANGE;
            bucket[bucketId].write(value);
            c.register(value);
        }

        for (int i = 0; i < bucket.length; i++) { // submit non-empty buffers
            bucket[i].submitBuffer();
        }

        byte[] compressProperties = null;
        for (int i = 0; i < bucket.length; i++) { // compress the data
            compressProperties = bucket[i].compressData();
        }

        printStatistics();

        for (int i = 0; i < bucket.length; i++) { // decode & sort buckets one by one
            int[] array = bucket[i].decompress(compressProperties);
            Arrays.sort(array);

            for(int v : array) {
                c.consume(v);
            }
        }
        c.finalCheck();
    }

    public void printStatistics() {
        int size = 0;
        int sizeCompressed = 0;

        for (int i = 0; i < BUCKETS; i++) {
            int bucketSize = 4*bucket[i].size;
            size += bucketSize;
            sizeCompressed += bucket[i].compressedOut.size();

            System.out.println("  bucket[" + i
                    + "] contains: " + bucket[i].size
                    + " numbers, compressed size: " + bucket[i].compressedOut.size()
                    + String.format(" compression factor: %.2f", ((double)bucket[i].compressedOut.size())/bucketSize));
        }

        System.out.println(String.format("Data size: %.2fM",(double)size/(1014*1024))
                + String.format(" compressed %.2fM",(double)sizeCompressed/(1014*1024))
                + String.format(" compression factor %.2f",(double)sizeCompressed/size));
    }
}

static class Consumer {
    private Set<Integer> values = new HashSet<>();

    int v = -1;
    public void consume(int value) {
        if(v < 0) v = value;

        if(v > value) {
            throw new IllegalArgumentException("Current value is greater than previous: " + v + " > " + value);
        }else{
            v = value;
            values.remove(value);
        }
    }

    public void register(int value) {
        values.add(value);
    }

    public void finalCheck() {
        System.out.println(values.size() > 0 ? "NOT OK: " + values.size() : "OK!");
    }
}

public static void main(String[] args) throws IOException {
    Producer p = new Producer();
    Consumer c = new Consumer();
    Sorter sorter = new Sorter();

    sorter.doSort(p, c);
}
}

对于随机数，它产生如下结果:

bucket[0] contains: 200357 numbers, compressed size: 353679 compression factor: 0.44
bucket[1] contains: 199465 numbers, compressed size: 352127 compression factor: 0.44
bucket[2] contains: 199682 numbers, compressed size: 352464 compression factor: 0.44
bucket[3] contains: 199949 numbers, compressed size: 352947 compression factor: 0.44
bucket[4] contains: 200547 numbers, compressed size: 353914 compression factor: 0.44
Data size: 3.85M compressed 1.70M compression factor 0.44

对于一个简单的升序序列(使用一个桶)，它产生:

bucket[0] contains: 1000000 numbers, compressed size: 256700 compression factor: 0.06
Data size: 3.85M compressed 0.25M compression factor 0.06

EDIT

结论:

不要试图欺骗大自然 使用更简单的压缩和更低的内存占用 确实需要一些额外的线索。普通的防弹方案似乎并不可行。

第二阶段:强化压缩，最终结论

正如在前一节中已经提到的，任何合适的压缩技术都可以使用。因此，让我们摒弃LZMA，转而采用更简单、更好(如果可能的话)的方法。有很多好的解决方案，包括算术编码，基树等。

无论如何，简单但有用的编码方案将比另一个外部库更能说明问题，它提供了一些漂亮的算法。实际的解决方案非常简单:因为存在部分排序的数据桶，所以可以使用增量而不是数字。

随机输入测试结果稍好:

bucket[0] contains: 10103 numbers, compressed size: 13683 compression factor: 0.34
bucket[1] contains: 9885 numbers, compressed size: 13479 compression factor: 0.34
...
bucket[98] contains: 10026 numbers, compressed size: 13612 compression factor: 0.34
bucket[99] contains: 10058 numbers, compressed size: 13701 compression factor: 0.34
Data size: 3.85M compressed 1.31M compression factor 0.34

示例代码

  public static void encode(int[] buffer, int length, BinaryOut output) {
    short size = (short)(length & 0x7FFF);

    output.write(size);
    output.write(buffer[0]);

    for(int i=1; i< size; i++) {
        int next = buffer[i] - buffer[i-1];
        int bits = getBinarySize(next);

        int len = bits;

        if(bits > 24) {
          output.write(3, 2);
          len = bits - 24;
        }else if(bits > 16) {
          output.write(2, 2);
          len = bits-16;
        }else if(bits > 8) {
          output.write(1, 2);
          len = bits - 8;
        }else{
          output.write(0, 2);
        }

        if (len > 0) {
            if ((len % 2) > 0) {
                len = len / 2;
                output.write(len, 2);
                output.write(false);
            } else {
                len = len / 2 - 1;
                output.write(len, 2);
            }

            output.write(next, bits);
        }
    }
}

public static short decode(BinaryIn input, int[] buffer, int offset) {
    short length = input.readShort();
    int value = input.readInt();
    buffer[offset] = value;

    for (int i = 1; i < length; i++) {
        int flag = input.readInt(2);

        int bits;
        int next = 0;
        switch (flag) {
            case 0:
                bits = 2 * input.readInt(2) + 2;
                next = input.readInt(bits);
                break;
            case 1:
                bits = 8 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 2:
                bits = 16 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 3:
                bits = 24 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
        }

        buffer[offset + i] = buffer[offset + i - 1] + next;
    }

   return length;
}

请注意，这种方法:

不消耗大量内存 使用流 提供了不那么坏的结果

完整的代码可以在这里找到，BinaryInput和BinaryOutput实现可以在这里找到

最终结论

没有最终结论:)有时候，从元级别的角度来回顾一下任务，这确实是个好主意。

花点时间完成这个任务很有趣。顺便说一下，下面有很多有趣的答案。感谢您的关注和愉快的编码。

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个。

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

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

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

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

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