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

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

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

特别地，爆发排序非常适合这种情况。另外，由于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倍。

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

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

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

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

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

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

参见维基百科的文章:

堆排序 二叉堆

虽然公认的答案完美地回答了问题的描述，但我已经到达了这个地方，徒劳地寻找一种算法将一个数组内联划分为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;
  }

你会想看一看博士们的大规模基因组序列处理。笠原和森下。

由四个核苷酸字母A、C、G和T组成的字符串可以特别编码为整数，以便更快地处理。基数排序是书中讨论的许多算法之一;您应该能够适应这个问题的公认答案，并看到一个很大的性能改进。

基数排序不是缓存意识，也不是对大集最快的排序算法。 你可以看看:

ti7qsort。Ti7qsort是对整数最快的排序(可用于固定大小的小字符串)。 内联QSORT 字符串排序

您还可以使用压缩并将DNA的每个字母编码为2位，然后存储到排序数组中。