如果你的数据集如此之大，那么我认为基于磁盘的缓冲区方法是最好的:

sort(List<string> elements, int prefix)
    if (elements.Count < THRESHOLD)
         return InMemoryRadixSort(elements, prefix)
    else
         return DiskBackedRadixSort(elements, prefix)

DiskBackedRadixSort(elements, prefix)
    DiskBackedBuffer<string>[] buckets
    foreach (element in elements)
        buckets[element.MSB(prefix)].Add(element);

    List<string> ret
    foreach (bucket in buckets)
        ret.Add(sort(bucket, prefix + 1))

    return ret

我也会尝试分组到更大数量的桶，例如，如果你的字符串是:

GATTACA

第一个MSB调用将返回GATT的桶(总共256个桶)，这样就可以减少基于磁盘的缓冲区的分支。这可能会提高性能，也可能不会，所以不妨尝试一下。

我将对字符串的打包位表示进行burst排序。突发排序被认为比基数排序有更好的局部性，用突发尝试代替经典尝试减少了额外的空间使用。原始论文有测量。

“没有多余空间的基数排序”就是一篇针对你的问题的论文。

dsimcha的MSB基数排序看起来不错，但是Nils更接近问题的核心，他观察到缓存的局部性是在大问题规模下造成问题的原因。

我建议一个非常简单的方法:

根据经验估计基数排序有效的最大大小m。 一次读取m个元素块，对它们进行基数排序，然后将它们写入(如果有足够的内存，则写入内存缓冲区，否则写入文件)，直到耗尽所有输入。 对结果排序块进行归并排序。

归并排序是我所知道的对缓存最友好的排序算法:“从数组A或B中读取下一项，然后将一项写入输出缓冲区。”它在磁带驱动器上有效地运行。它确实需要2n个空间来排序n个项目，但我敢打赌，您将看到的大大改进的缓存位置将使这一点变得不重要——如果您使用的是非就地基数排序，无论如何您都需要额外的空间。

最后请注意，归并排序可以在没有递归的情况下实现，事实上，这样做可以明确真正的线性内存访问模式。

我将冒个险，建议您切换到堆/堆排序实现。这个建议伴随着一些假设:

您可以控制数据的读取 你可以做一些有意义的排序数据，只要你“开始”得到它排序。

堆/堆排序的美妙之处在于，您可以在读取数据时构建堆，并且可以在构建堆的那一刻开始获得结果。

让我们后退一步。如果您非常幸运，可以异步读取数据(也就是说，您可以发布某种类型的读请求，并在某些数据准备就绪时收到通知)，那么您可以在等待下一个数据块进入(甚至来自磁盘)时构建堆的一块。通常，这种方法可以将一半排序的成本隐藏在获取数据所花费的时间之后。

读取数据之后，第一个元素就已经可用了。这取决于您将数据发送到哪里，这可能很棒。如果你要把它发送给另一个异步阅读器，或者一些并行的“事件”模型，或者UI，你可以不断地发送数据块。

也就是说，如果您无法控制如何读取数据，并且它是同步读取的，并且在完全写入之前对排序的数据没有任何用处，那么请忽略所有这些。：(

参见维基百科的文章:

堆排序 二叉堆

看起来您已经解决了这个问题，但是为了记录，似乎有一种可行的就地基数排序是“美国国旗排序”。这里描述了:工程基数排序。一般的想法是对每个字符进行2次传递——首先计算每个字符有多少个，这样就可以将输入数组细分为箱子。然后再执行一遍，将每个元素交换到正确的bin中。现在递归地对每个箱子的下一个字符位置排序。