

安定な比較ソートを開発しています。  
平均計算時間で最速なものを目指しています。  
ソートされるデータ以外の格納領域が O(n) ぐらいは使用して良いと思っています。

安定でない比較ソートであれば、クイックソートが最速なのだと思っています。

glibc の qsort は  
malloc に成功すれば 16*n バイトぐらい O(n) 格納領域を使用し  
マージソートを実行します。なので安定です。

newlib の qsort は 30年近く使われているもので、安定でない比較ソートです。

そして、glibc と newlib の qsortを競争させると  
ソートデータの条件により、勝ったり負けたりです。

ソートデータの条件は大きく分けて、次の４つがあると思います。

  1. 比較関数の重さ。
  2. 要素サイズの大きさ。
  3. 要素数。
  4. キー値の偏り。 
    * A. 社員番号など同一キーがない場合
    * B. 都道府県コード(番号)など
    * C.男女など

安定な比較ソートに限って、平均計算時間で比較する場合、どのアルゴリズムが最高速と言えるのでしょうか？

例えば、次の中ではどれが速いのでしょうか？  
[ソート -
Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88#.E5.AE.89.E5.AE.9A.E3.82.BD.E3.83.BC.E3.83.88)


CC BY-SA 4.0
2019-07-20T05:19:07.763
56767
2019-07-20T09:11:53.923
2019-07-20T09:11:53.923
29826
35178
question
c アルゴリズム sort
安定な比較ソートでの最高速アルゴリズムはなんですか？