ソートアルゴリズム とは？

同じ結果でも、比べ方や移動の手順が違うからだよ。クイックソートは基準の値を使って分割し、マージソートは分けて整列した列を併合する。データ量や元の並び、追加メモリなどで向き不向きが変わるんだ。

保証はないよ。NISTの説明では典型的な計算量はO(n log n)だけれど、最悪の場合はO(n²)になる。マージソートはO(n log n)。計算量はデータ数に対する増え方で、実際の秒数や、すべての環境での順位を示すものではないよ。

同じキーのデータが、元の相対的な順番を保つことだよ。点数が同じ生徒を並べたとき、その生徒同士の元の順序が残るイメージ。Pythonのsortedやlist.sortは安定性を保証し、ECMAScriptのArray.prototype.sortにも安定性の要件があるよ。

まず言語の標準機能と、その並べ方の指定を確認するとよいね。Pythonならsortedで新しいリストを作り、list.sortなら元のリストを並べ替える。名前や点数などのキーも指定できる。内部のアルゴリズムや保証は、言語や実装の資料で確かめよう。

比較以外の方法もあるよ。カウンティングソートは各キーの出現数を数え、配置を決める。NISTは、データ数に比べてキーの種類が少ない場合に効率的と説明している。値の範囲や必要なメモリを含めて考え、条件なしにO(n)で最速とは言わないんだ。