ソートについて

UWSCでソート処理を考えたついでに考えた。
ソートアルゴリズムはどれを使うべきだろうか？
並列処理を考えないのであれば、以下の通りと思う。

1. O(n)のメモリーを使って良い？
   1. Yes: QuickSort（メモリー使用で安定化）のワーストケースが怖い？
      1. Yes: MergeSort
      2. No : QuickSort（ワーストケースは、境界値が極端な値をとり続けた場合）
   2. No : 安定ソートでないとダメ？
      1. Yes: In-place MergeSort
      2. No : QuickSortのワーストケースが怖い？、、、てかQuickSortのメモリ使用量はO(1)じゃない？
         1. Yes: CombSort
         2. No : QuickSort

CombSort、かなり優秀に思った。
MergeSortは、もちろん優秀。
再帰を使わない実装にして、使用メモリーは最大n/2。

QuickSortは再帰を使わない実装が思いつかないのが良くないところ。
（自前スタックを用意してのループは、再帰と同じ）
ゆえに、メモリーがシビアな場合、In-place MergeSortかCombSortの二択。
安定ソート以外はごみ、と言われるなら、メモリー使用量順に
QuickSort(インデックス配列で安定化) > MergeSort > In-place MargeSort
速度もだいたい同じ順序。