ヒープソート

クイックソートの平均計算量は $O(N \log_2 N)$ だが, 最悪の場合 $O(N^2)$ となる. ここでは最悪でも $O(N \log_2 N)$ でソートできるアルゴリズムを 一つ紹介する.