ソート
効率的なソートは、ソート済みのデータを必要とする他のアルゴリズム(探索やマージ)の最適化にとっても重要である。また、ソートされたデータの方が人間にとっても読みやすい。形式的には、その出力は以下の2つの条件を満たさなければならない。
設定された順序(昇順または降順)に対して、逆になるような順序の出力があってはならない。
出力は入力の並べ替えでなければならない。
情報工学や計算機科学の黎明期から、ソートは単純な問題でありながら効率的に解くことが難しく、そのためもあって盛んに研究されてきた。例えばバブルソートについては、早くも1956年には解析が行われている。しかし、21世紀初にも新たなソートアルゴリズムが発明されている(例えば、Timsort(英語版)は2002年に、図書館ソートは2004年に発表された)。すでに考案されているソートにも様々なアルゴリズムがあり、またアルゴリズムという概念を学習するのに最適なので、情報工学や計算機科学での入門的題材として広く親しまれている。例えば、分割統治法、データ構造、乱択アルゴリズム、計算量解析、O記法、時間と空間のトレードオフ、下限などが含まれる。
グラフィカルユーザインタフェース (GUI) においてよく使われるウィジェットのひとつとしてリストビュー (list view) が挙げられるが、各レコードのフィールドを表す任意のカラムについてリスト中のアイテムを昇順/降順ソートできるようになっていることが多い。
よって、 m > log 2  ( n e ) n = n ( log 2  n − log 2  e ) {\displaystyle m>\log _{2}\left({\frac {n}{e}}\right)^{n}=n(\log _{2}n-\log _{2}e)} 。よって m = Ω ( n log  n ) {\displaystyle m=\Omega (n\log n)} 。
以上より、任意の比較ソートアルゴリズムの最悪計算量は Ω ( n log  n ) {\displaystyle \Omega (n\log n)} となる。すなわち、比較ソートアルゴリズムの最悪計算量の下界は漸近的には n log  n {\displaystyle n\log n} となる。
マージソート、ヒープソートなどの比較ソートアルゴリズムの最悪計算量は O ( n log  n ) {\displaystyle O(n\log n)} であるため、これらのアルゴリズムの最悪計算量は上記の下界と漸近的に一致していると言える。つまり、これらのアルゴリズムの最悪計算量は漸近的に最適である。