可能性の重複：
Fastest sort of fixed length 6 int array8つの要素をソートし、より良い方法がない（より効率的な方法ではない）ことを証明する最良の方法を見つけるにはどうすればよいですか？
タスクは比較の少なくとも数（ない操作）で8個の乱数をソートする方法を見つけることです。私はqSortを使用する必要があると期待しています（配列を半分に分け、ソートしてからマージするなど..クイックソートだと思います）。 8要素の比較数は17で、16（n-1）の比較でランダムな配列をソートする方法がないことを証明しなければなりません。
ありがとうございました
いずれの場合も最悪である必要があります。私は研究の初年度だから、何か特別なことをする必要はないと思う（ITではなく数学を学ぶ）。私が使うソートの種類は、mergesortです！前もって感謝します。
Mergesort /マージ挿入ソートでは、最小の最悪ケースの比較数であるn = 8に対して16回の比較が必要です。
http://oeis.org/A001768（マージのための比較の数）
http://oeis.org/A036604（一般的には比較の最小数）
は Sorting an array with minimal number of comparisons
EDITも参照： "乱数" を仮定しない範囲制限整数です。値の範囲について仮定することができれば、選択肢があります。
基数ソートはまったく比較する必要はありません。
それが比較ではないからといって、比較を必要としないというわけではありません。単純なx == xでも比較です。数字同士の比較は比較です... –
@Luchian Grigore：ソートとバケットソートのような基数ソートは、汎用ソートアルゴリズムではありません。これは、入力に追加の条件を必要とします。クイックソート、マージソート、その他の真の汎用ソートアルゴリズムと同様に、任意の入力をソートすることはできません。 –
分割、ソート、マージはマージソートでありクイックソートではありません。 –
ベストケース？平均的なケース？最悪の場合？確率論的アルゴリズムは許されていますか？私は、7回の比較で最良の実装を与えることができます。 – thiton
@atalyorによってリンクされた質問で選択された回答にあるリンクを使用すると、ネットワークソートは19の比較を使用します。 – hatchet