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

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

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

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

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

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

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

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

例えば、次の中ではどれが速いのでしょうか？
ソート - Wikipedia