分割統治法によるクイックソートを使う

クイックソート (quick sort) は、基準値（ピボット）を1つ選び、配列を「ピボットより小さい要素」と「ピボット以上の要素」に分ける 分割（partition） を行い、その両側に同じ処理を再帰的に適用することで整列する比較ソートである。分割が一度の走査で済むため、平均的に高速に動作する。

  1. ピボットの選択: 部分配列の先頭・末尾・中央などから1要素をピボットとして選ぶ（実装により様々な選び方がある）。
  2. 分割: ピボットを基準に、左側にピボット未満の要素、右側にピボット以上の要素が来るように要素を並べ替える。ピボット自体は最終的な位置に置かれる。
  3. 再帰: ピボットの左側の部分配列と右側の部分配列に対して、要素が1つ以下になるまで手順1〜2を繰り返す。
procedure quick_sort(A, lo, hi)
  if lo >= hi then
    return
  p = partition(A, lo, hi)
  quick_sort(A, lo, p - 1)
  quick_sort(A, p + 1, hi)

procedure partition(A, lo, hi)
  pivot = A[hi]
  i = lo
  for j from lo to hi - 1
    if A[j] < pivot then
      swap(A[i], A[j])
      i = i + 1
  swap(A[i], A[hi])
  return i

期待時間計算量は O(n log n) で、ピボットの選び方が悪いと（すでにソート済みなど）最悪 O(n²) に落ちる。空間計算量は実装次第だが、再帰のスタックを除けば原則として O(1) の追加領域で済む インプレース の実装が多い。等しいキーの相対順序を保たない 不安定 なソートであることが一般的である。

バブルソートのような単純な O(n²) の手法と比べ、データ規模が大きいときの実効速度が有利になりやすい。標準ライブラリの sort では、言語・実装によってクイックソートに近い戦略が採用されていることも多い。