クイックソート
クイックソートの効率は配列の分割の効率に左右される。再帰の各段階で常に均等に分割される場合が最良であり、時間計算量は O ( n log  n ) {\displaystyle O(n\log n)} となる。一方で、常に「1要素と残り全部」のように偏って分割された場合が最悪のケースで、時間計算量が O ( n 2 ) {\displaystyle O(n^{2})} に悪化する。
最悪ケースを避けるにはピボットの選択に注意を払う必要がある。たとえば、既にソートされた配列に対して先頭や末尾の要素をピボットとすると最悪ケースとなる。なるべく配列の中央値をピボットとして選べるようにすれば、このようなケースを回避できる。
代表的なピボット選択の戦略として、以下のようなものが挙げられる:
配列の一部の要素を選び、それらの中央値を選ぶ(典型的には、配列の先頭・中間・末尾の3要素の中央値)
ランダムに配列要素を選ぶ(真の乱数による配列選択を仮定すれば、人為的に最悪ケースを与えることが不可能になる)
また、ピボットを選ぶ前に配列をランダムに並べ替えるなどの手法によっても、ソートに最悪計算時間を要する可能性を抑えられる。
ただし、いずれの場合も最悪ケースの可能性を完全に排除できるものではない。これに対する根本的な改良として、一定の閾値よりも再帰が深くなったらヒープソートのような O ( n log  n ) {\displaystyle O(n\log n)} 時間が保証されるアルゴリズムに切り替える方法がある(イントロソート)。
確定した部分は太文字で表す。ピボットには下線を引く。
初期データ: 8 4 3 7 6 5 2 1
中央付近に位置する7をピボットとする。左から7以上を探索して8を発見。右から7未満を探索して1を発見。前者が左にあるため入れ替え。 1 4 3 7 6 5 2 8
次の位置から探索を継続。7と2を発見して入れ替え。 1 4 3 2 6 5 7 8
次の位置から探索を継続。7と5を発見。前者が右にあるため探索終了。左からの探索で最後に発見した位置(7の位置)の左で分割。 1 4 3 2 6 5 | 7 8
「1 4 3 2 6 5」の領域で2をピボットとして探索。左からの探索で4、右からの探索で2を発見、前者が左にあるため入れ替え。 1 2 3 4 6 5 | 7 8
次の位置から探索を継続。3と2を発見。前者が右にあるため探索終了。3の左で分割。 1 2 | 3 4 6 5 | 7 8
「1 2」の領域を2をピボットとして探索、双方とも2を発見、同じ位置であるため探索終了。