ヒープソートを使用する

ヒープソート (heap sort) は、配列を 二分ヒープ の形に整え、その根に常に最大値が来る性質を利用して、根と末尾を入れ替えて確定させながらヒープを縮めていく インプレース の比較ソートである。

  1. 準備: 配列をインデックス付きの完全二分木とみなす。親 i (i >= 0) に対し左の子は 2i+1、右の子は 2i+2 になる。
  2. 構築: 親の値が子の値以上という条件を満たすよう、葉に近い内部ノードから順に沈降して 最大ヒープ にする。
  3. 抽出: 根（位置 0）が全体の最大なので、それと ヒープの末尾 を交換する。末尾側はもうソート済み領域として固定し、残り [0 .. heapEnd-1] だけをヒープとして見なす。
  4. 反復: 新しい根がヒープ条件を満たすまで子と比較・交換して下へ沈める。ヒープ長が 1 になるまで手順 3〜4 を繰り返す。
procedure heap_sort(A)
  n = length(A)
  for i from floor(n / 2) - 1 down to 0
    sift_down(A, i, n)
  for end from n - 1 down to 1
    swap(A[0], A[end])
    sift_down(A, 0, end)

procedure sift_down(A, start, heap_end)
  i = start
  while true
    l = 2 * i + 1
    r = 2 * i + 2
    largest = i
    if l < heap_end and A[l] > A[largest] then
      largest = l
    if r < heap_end and A[r] > A[largest] then
      largest = r
    if largest = i then
      break
    swap(A[i], A[largest])
    i = largest

最悪・平均・最良いずれも時間計算量は O(n log n) で、追加の配列を使わない標準実装では 空間計算量は O(1)（再帰を使わない実装が一般的）。同一キーの相対順序を保たない 不安定 なソートであることが多い。

バブルソートの O(n²) と比べて大きな入力では優位になりやすく、クイックソートと異なり 最悪でも O(n log n) に抑えられる反面、定数倍やキャッシュ効率では実装やデータに依存してクイックソートに劣ることもある。

優先度付きキューの内部にもヒープが使われるため、アルゴリズムの理解はヒープソートだけでなく広い実装の読み取りにもつながる。