効果的な機能的ソート

Question

私はaの関数をプログラミングしています ti-nspire, 、そのため、関数内からビルトインを使用することはできません。リスト自体を変更せずに数値のリストをソートするための最も一般的に効率的なアルゴリズムは何ですか？ （数学の一般的な使用と同様に、再帰とリスト分割は公正なゲームです。）

Answer 1

Mergesortは簡単で、シンプルで、効率的で、安定しています。リストを分割し、再帰的にソートし、結果をマージします。

より具体的には、mergesortはo（n log n）を取ります。これは漸近的に最適です。また、実際には（両方のアルゴリズムが特別な目的の種類で短いサブリストをソートするように変更された）、MergESORTは、C/C ++標準ライブラリで使用される修正されたクイックソートの緊密な競争相手になります。

編集：クイックソートや挿入ソートなどのインプレースソートとは異なり、MergESORTは補助メモリが必要であり、スワッピングするのではなくコピーすることで実装するのが最も簡単です。

Answer 2

ティムソート PythonとJava SE 7で使用されています。これは、マージソートと挿入ソートを最大限に活用します。挿入ソートはO（n^2）ですが、数字の小さなリストでは、マージソートよりも高速です！

したがって、これを述べたように一般的なソートアルゴリズムとして使用できます ここ