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

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个桶)，这样就可以减少基于磁盘的缓冲区的分支。这可能会提高性能，也可能不会，所以不妨尝试一下。

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

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

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

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

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

我从未见过就地基数排序，从基数排序的性质来看，只要临时数组适合内存，我怀疑它比就地排序快得多。

原因:

排序对输入数组进行线性读取，但所有写入几乎都是随机的。从特定的N开始，这可以归结为每次写入的缓存丢失。这种缓存缺失会减慢你的算法。它是否到位并不会改变这种效果。

我知道这不能直接回答您的问题，但是如果排序是一个瓶颈，那么您可能想要看看作为预处理步骤的近似排序算法(软堆上的wiki-page可以让您开始)。

这可以很好地提高缓存的局部性。课本上的错位基数排序会表现得更好。写入仍然几乎是随机的，但至少它们会聚集在相同的内存块周围，这样就增加了缓存命中率。

但我不知道这在实践中是否可行。

顺便说一句:如果你只处理DNA字符串:你可以将一个字符压缩成两个比特，并打包大量数据。这将把内存需求减少到原始表示的四倍。寻址变得更加复杂，但无论如何，CPU的ALU在所有缓存丢失期间都有大量的时间。

这是DNA的MSD基排序的一个简单实现。它是用D语言写的，因为这是我最常用的语言，因此最不可能犯愚蠢的错误，但它可以很容易地翻译成其他语言。它是到位的，但需要2 * seq。Length通过数组。

void radixSort(string[] seqs, size_t base = 0) {
    if(seqs.length == 0)
        return;

    size_t TPos = seqs.length, APos = 0;
    size_t i = 0;
    while(i < TPos) {
        if(seqs[i][base] == 'A') {
             swap(seqs[i], seqs[APos++]);
             i++;
        }
        else if(seqs[i][base] == 'T') {
            swap(seqs[i], seqs[--TPos]);
        } else i++;
    }

    i = APos;
    size_t CPos = APos;
    while(i < TPos) {
        if(seqs[i][base] == 'C') {
            swap(seqs[i], seqs[CPos++]);
        }
        i++;
    }
    if(base < seqs[0].length - 1) {
        radixSort(seqs[0..APos], base + 1);
        radixSort(seqs[APos..CPos], base + 1);
        radixSort(seqs[CPos..TPos], base + 1);
        radixSort(seqs[TPos..seqs.length], base + 1);
   }
}

显然，这是特定于DNA的，而不是普遍的，但它应该很快。

编辑:

我很好奇这个代码是否真的有效，所以在等待我自己的生物信息学代码运行时，我对它进行了测试/调试。上面的版本现在已经经过测试并且可以工作。对于1000万个每个5个碱基的序列，它比优化的引入排序快大约3倍。

在性能方面，您可能希望查看更通用的字符串比较排序算法。

目前，您将触及每个字符串的每个元素，但您可以做得更好!

特别地，爆发排序非常适合这种情况。另外，由于burstsort是基于try的，它对于DNA/RNA中使用的小字母非常有效，因为你不需要在trie实现中构建任何形式的三元搜索节点、散列或其他三节点压缩方案。这些尝试对于类似后缀数组的最终目标也很有用。

burstsort的一个不错的通用实现可以在源代码forge (http://sourceforge.net/projects/burstsort/)上找到——但还不到位。

为了进行比较，http://www.cs.mu.oz.au/~rsinha/papers/SinhaRingZobel-2006.pdf基准测试中涵盖的C-burstsort实现对于一些典型的工作负载比快速排序和基数排序快4-5倍。

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

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个桶)，这样就可以减少基于磁盘的缓冲区的分支。这可能会提高性能，也可能不会，所以不妨尝试一下。