小さな配列（32または64要素以下）の高速安定ソート

Question

一般的な知恵は、十分に小さい配列の場合、挿入ソートが最適であると言います。たとえば、Timsortは、64要素までの配列に対して（バイナリ）挿入ソートを使用します。

ような再帰次いでソートされる小さなサブリストにリストを分割してクイックソートやマージソートのようないくつかの分割統治アルゴリズム：Wikipediaから。これらのアルゴリズムの実際の最適な最適化は、小さなソートリストをソートするために挿入ソートを使用することです。挿入ソートはこれらのより複雑なアルゴリズムよりも優れています。挿入のソートに利点があるリストのサイズは、環境と実装によって異なりますが、通常は8〜20の要素です。

これは実際には正しいですか？より良い選択肢はありますか？

プラットフォームによって大きく異なる場合は、.NETに最も興味があります。

Answer 1

はい、これは私のアルゴリズムクラスで学んだことです。 C++ STL。ウィキペディアから：

不安定なソートの2000年6月SGI C++標準 テンプレートライブラリstl_algo.h 実装は、中央値の、パラメータとして渡された をヒープソートに切り替え 再帰の深さとアプローチイントロソート マッサーを使用しています-3 ピボット選択とSedgewick 最終挿入ソートパス。シンプル 挿入ソートに切り替えるための要素 しきい値は

16.私は昨年、いくつかの非公式のパフォーマンステストをやったし、C++のSTLのstd ::ソートは、.NETでのArray.sortの約2倍の速さでした。私は.NET Array.Sortがどのように実装されているのかはわかりませんが、.NETでは配列のアクセスにはC++とは異なり、パフォーマンスの違いを大きく説明する境界チェックが必要です。

Answer 2

.NETはraw machinecodeにコンパイルされない言語です。私はAPI関数（ネイティブコードを使用しています）を呼び出すのがおそらく最速の方法だと言います。

Answer 3

私は、それが本当に比較機能がどれだけの仕事をしているかによって決まります。ワークシートの行を間接的にソートしていて、各比較で行を取得して複数の列を比較したり、数値と文字列の比較を混在させたりすると、遅くなることがあります。

一方、配列の長さが短い場合は、秒単位で何回ソートする必要があるかによって決まります。なぜなら、相対的に遅い場合でも、気付かないかもしれないからです違い。

疑問がある場合は、マージソートをコーディングして、それに進みます。私はqsortが安定しておらず、時には長い時間がかかるという悪い経験をしています。手書きのマージソートは単純で信頼性があり、十分に高速です。

Answer 4

小さなリストの挿入ソートより高速なO（n log n）アルゴリズムはありません。しかし、競合するいくつかのO（n^2）アルゴリズムがあります。特に、選択ソートはこれらのうちの1つではありませんが、スワップや移動が高価なまれな状況下では優れています。バブルの並べ替えや変形も単なる一般的ではありません。

ネットワークソート：ソートアルゴリズムです。常に安定しており、分岐はありません。それは全体的にひどいスペックを持っていますが、ブランチはほとんどのリストでは恒星のパフォーマンスを意味しません。基本ケースは次のとおりです。if(a<b) swap(a,b);

バッチによる挿入ソート：各ループで2-4要素をソートし、それらを一緒に挿入します。これにより、移動回数が削減され、長いリストの場合は25〜37％の比較が行われます。全体的な効果は、16〜64のサイズ範囲のリストの最適化です。