请以我们选择的语言提供代码示例。

更新：
外部存储没有设置任何限制。

示例：通过网络接收/发送整数。本地磁盘上有足够的空间可产生中间结果。

解决方案

1百万个32位整数= 4 MB内存。

我们应该使用某种使用外部存储的算法对它们进行排序。例如，Mergesort。

将问题分解成足够小以适合可用内存的部分，然后使用合并排序将它们合并。

我们需要提供更多信息。还有什么额外的可用存储空间？我们应该将结果存储在哪里？

否则，最一般的答案是：
1.将第一部分数据加载到内存(2MB)中，用任何方法对其进行排序，然后输出到文件中。
2.将数据的后半部分加载到内存(2MB)中，通过任何方法对其进行排序，然后将其保留在内存中。
3.使用合并算法合并两个已排序的两半并将完整的已排序数据集输出到文件。

正如上面提到的，键入32位4 MB的int值。

使用C ++中的int，short和char类型将尽可能多的" Number"放入尽可能少的空间。通过执行多种类型的转换以在各处填充东西，我们可能会很聪明(但有奇怪的脏代码)。

在这里，它不在我座位的边缘。

小于2 ^ 8(0 255)的任何内容都作为char存储(1字节数据类型)

小于2 ^ 16(256 65535)和大于2 ^ 8的任何内容都存储为short(2字节数据类型)

其余的值将被放入int中。 (4字节数据类型)

我们可能想要指定char节的开始和结束位置，short节的开始和结束位置以及int节的开始和结束位置。

这篇有关外部排序的维基百科文章提供了一些有用的信息。

双重锦标赛排序与多相合并

#!/usr/bin/env python
import random
from sort import Pickle, Polyphase

nrecords = 1000000
available_memory = 2000000 # number of bytes
    #NOTE: it doesn't count memory required by Python interpreter 

record_size = 24 # (20 + 4) number of bytes per element in a Python list
heap_size = available_memory / record_size 
p = Polyphase(compare=lambda x,y: cmp(y, x), # descending order
              file_maker=Pickle, 
              verbose=True,
              heap_size=heap_size,
              max_files=4 * (nrecords / heap_size + 1))

# put records
maxel = 1000000000
for _ in xrange(nrecords):
    p.put(random.randrange(maxel))

# get sorted records
last = maxel
for n, el in enumerate(p.get_all()):
    if el > last: # elements must be in descending order
        print "not sorted %d: %d %d" % (n, el ,last)
        break
    last = el

assert nrecords == (n + 1) # check all records read

没有示例，但是存储桶排序具有相对较低的复杂度，并且易于实施

Guido van Rossum使用Python在2MB RAM中对一百万个32位整数进行排序

• 嗯，将它们全部存储在一个文件中。
• 内存映射文件(我们说过只有2M的RAM；让我们假设地址空间足够大，可以内存映射文件)。
• 使用文件后备存储对它们进行排序，就好像它现在是真实内存一样！