ソート
入力されるリストの項目数 n に基づいた計算量による分類。典型的なソートアルゴリズムでは、最善で O(n log n) 、最悪で O(n) である。理想は O(n) である。
比較ソートでは、一般的な(ランダムに並んだ)データの並べ替えに対しては少なくとも O(n log n) の比較回数が必要である。(→#比較ソートの理論限界)
計算機科学では、ソートアルゴリズムを次のように分類する。
ソート (英: sort) は、データの集合を一定の規則に従って並べること。日本語では整列(せいれつ)、並べ替え(ならべかえ)、分類(ぶんるい)などと訳される。
主に配列や連結リストのような、リストデータ構造に分類されるコレクション(コンテナ)に格納されている要素データを、全順序関係によって並べ替えることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順(しょうじゅん、英: ascending order)を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順(こうじゅん、英: descending order)という。
対象となるコレクションのデータ構造や必要とされる出力、また時間的コストと空間的コストの兼ね合いによって、ソートに使われるアルゴリズムは異なる。