我改变主意了; 我实际上喜欢@Ryan的基数排序思想，只是我会针对此特定问题进行一些调整。
假设有太多的数字以致它们无法容纳在内存中，但是我们拥有了所需的所有磁盘。（鉴于问题的措辞方式，这并非不合理。）
调用输入文件A和B。
因此，创建512个新文件；称它们为文件A_0至A_255，以及文件B_0至B_255。文件A_0从文件A的高字节为0的所有数字。文件A_1从文件A的高字节为1的所有数字。文件B_37从文件B的高字节为37的所有数字。依此类推。
现在，所有可能的重复项都位于（A_0，B_0），（A_1，B_1）等中，并且可以对这些对进行独立分析（并在必要时进行递归分析）。并且所有磁盘访问都是合理的线性访问，这应该相当有效。（如果没有，请调整用于存储桶的位数...）
这仍然是O（n log n），但是它不需要随时将所有内容保存在内存中。（这里，在基数常数因子排序是log（2 ^ 64）或左右，所以它不是真正的线性，除非你有很多超过2 ^ 64个数字。即使是最大盘的可能性不大。）
[编辑，详细说明]
这种方法的全部目的是，您实际上不必对两个列表进行排序。也就是说，使用这种算法，您实际上无法随时按顺序枚举任一列表的元素。
一旦有了文件A_0，B_0，A_1，B_1，...，A_255，B_255，您将简单地观察到A_0中的数字不能与B_1，B_2，...，B_255中的任何数字相同。因此，您从A_0和B_0开始，找到这些文件共有的编号，将它们附加到输出中，然后删除 A_0和B_0。然后，对A_1和B_1，A_2和B_2等执行相同的操作。
要查找A_0和B_0之间的公共数字，只需递归...创建文件A_0_0，其中包含A_0的所有元素，第二个字节等于零。创建包含第二个字节等于1的A_0的所有元素的文件A_0_1。依此类推。一旦将A_0和B_0的所有元素存储到A_0_0至A_0_255和B_0_0至B_0_255中，就可以删除 A_0和B_0，因为您不再需要它们。
然后，您对A_0_0和B_0_0进行递归查找共同的元素，并在存储桶后立即将它们删除...依此类推。
当最终找到只有一个元素（可能重复）的存储桶时，您可以立即决定是否将该元素附加到输出文件中。
此算法绝不会消耗超过保存两个文件所需原始空间的2倍以上的ε，ε小于0.5％。（证明供读者练习。）
老实说，如果文件太大而无法容纳在内存中，我相信这是所有这些答案中最有效的算法。（作为一个简单的优化，如果“存储桶”足够小，您可以退回到std :: set解决方案。）