虽然公认的答案完美地回答了问题的描述，但我已经到达了这个地方，徒劳地寻找一种算法将一个数组内联划分为N部分。我自己也写过一个，就是这个。

警告:这不是一个稳定的分区算法，因此对于多层分区，必须对每个结果分区重新分区，而不是对整个数组重新分区。优点是它是内联的。

它有助于解决所提出的问题的方法是，您可以根据字符串中的一个字母重复进行内联分区，然后在分区足够小时使用您选择的算法对分区进行排序。

  function partitionInPlace(input, partitionFunction, numPartitions, startIndex=0, endIndex=-1) {
    if (endIndex===-1) endIndex=input.length;
    const starts = Array.from({ length: numPartitions + 1 }, () => 0);
    for (let i = startIndex; i < endIndex; i++) {
      const val = input[i];
      const partByte = partitionFunction(val);
      starts[partByte]++;
    }
    let prev = startIndex;
    for (let i = 0; i < numPartitions; i++) {
      const p = prev;
      prev += starts[i];
      starts[i] = p;
    }
    const indexes = [...starts];
    starts[numPartitions] = prev;
  
    let bucket = 0;
    while (bucket < numPartitions) {
      const start = starts[bucket];
      const end = starts[bucket + 1];
      if (end - start < 1) {
        bucket++;
        continue;
      }
      let index = indexes[bucket];
      if (index === end) {
        bucket++;
        continue;
      }
  
      let val = input[index];
      let destBucket = partitionFunction(val);
      if (destBucket === bucket) {
        indexes[bucket] = index + 1;
        continue;
      }
  
      let dest;
      do {
        dest = indexes[destBucket] - 1;
        let destVal;
        let destValBucket = destBucket;
        while (destValBucket === destBucket) {
          dest++;
          destVal = input[dest];
          destValBucket = partitionFunction(destVal);
        }
  
        input[dest] = val;
        indexes[destBucket] = dest + 1;
  
        val = destVal;
        destBucket = destValBucket;
      } while (dest !== index)
    }
    return starts;
  }

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

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个项目，但我敢打赌，您将看到的大大改进的缓存位置将使这一点变得不重要——如果您使用的是非就地基数排序，无论如何您都需要额外的空间。

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

你可以试着用trie。对数据排序就是简单地遍历数据集并插入数据集;结构是自然排序的，你可以把它想象成类似于b -树(除了不做比较，你总是使用指针指向)。

缓存行为将有利于所有内部节点，因此您可能无法在此基础上进行改进;但是您也可以修改树的分支因子(确保每个节点都适合单个缓存线，将树节点分配为类似于堆的节点，作为表示级别顺序遍历的连续数组)。由于try也是数字结构(对于长度为k的元素，O(k)插入/查找/删除)，因此您的性能应该优于基数排序。

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

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

原因:

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

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

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

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

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