高速ソート

次のサイズｎ（＝９）の配列ａを昇順にソートすることにします。
　　 ｉ　　１　　２　　３　　４　　５　　６　　７　　８　　９
　ａ[ｉ]　３０　８０　７０　１０　５０　２０　４０　９０　６０

基本的なソートの方法は「基本的なソート方法」で示しました。ここでは、高速なソート方法について概要を説明します。
　高速とは、計算量のオーダーが小さいことです。
　基本的なソート方法でのオーダーは Ｏ(ｎ²) であるのに対して、ここで取り扱う方法（シェルソートを除く）では Ｏ(ｎlog₂ｎ) です。

マージソート

配列を単純に２等分した区分にします。それぞれの区分内でソートされていれば、２つの区分をマージ（併合）することにより、全体がソートされます。区分内でソートされていない場合は、それをさらに２等分して、同様な操作を行います。これを繰り返すことにより全体がソートされた小さな区分になります。
　次に、それらの小区分を分割したときと逆の順序でマージすることにより、全体がソートされます。

数値例

　　　　　　　　　　　　　　　　　　　　　　　　　　　未：まだソートされていない
　　　　　　　　　　　　　　　　　　　　　　　　　　　済：既にソートされている
　　　　　　　　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　↑ア　　　　　　│３０│８０│７０│１０│５０│２０│４０│９０│６０│
　　│　　　　　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘
　　│　　　　　　　　　　　　　　　　　　　　│未
　　│　　　　　　　　　　　┌────────┴──────────┐
　　│　　　　┌──┬──┬──┬──┬──┐　　　　　┌──┬──┬──┬──┐
　　│イ　　　│３０│８０│７０│１０│５０│　　　　　│２０│４０│９０│６０│
　　　　　　　└──┴──┴──┴──┴──┘　　　　　└──┴──┴──┴──┘
　　分　　　　　　　　　　　│未　　　　　　　　　　　　　　　　　　│未
　　割　　　　　　　　┌──┴──────┐　　　　　　　　┌───┴────┐
　　　　　　┌──┬──┬──┐　　┌──┬──┐　　┌──┬──┐　　┌──┬──┐
　　│ウ　　│３０│８０│７０│　　│１０│５０│　　│２０│４０│　　│９０│６０│
　　│　　　└──┴──┴──┘　　└──┴──┘　　└──┴──┘　　└──┴──┘
　　│　　　　　　　　│未　　　　　　　　│済　　　　　　　│済　　　　　　　│未
　　│　　　　　┌──┴───┐　　　　　│　　　　　　　　│　　　　　　┌─┴──┐
　　↓　　┌──┬──┐　┌──┐　　　　│　　　　　　　　│　　　　　┌──┐　┌──┐
　　　エ　│３０│８０│　│７０│　　　　│　　　　　　　　│　　　　　│９０│　│６０│
　　↑　　└──┴──┘　└──┘　　　　│　　　　　　　　│　　　　　└──┘　└──┘
　　│　　　　　│済　　　　　│済　　　　│　　　　　　　　│　　　　　　│済　　　│済
　　│　　　　　└──┬───┘　　　　　│　　　　　　　　│　　　　　　└─┬──┘
　　│　　　┌──┬──┬──┐　　　　　│　　　　　　　　│　　　　　┌──┬──┐
　　　オ　　│３０│７０│８０│　　　　　│　　　　　　　　│　　　　　│６０│９０│
　　マ　　　└──┴──┴──┘　　　　　│　　　　　　　　│　　　　　└──┴──┘
　　ｌ　　　　　　　　└──┬──────┘　　　　　　　　└───┬────┘
　　ジ　　　　┌──┬──┬──┬──┬──┐　　　　　┌──┬──┬──┬──┐
　　　カ　　　│１０│３０│５０│７０│８０│　　　　　│２０│４０│６０│９０│
　　│　　　　└──┴──┴──┴──┴──┘　　　　　└──┴──┴──┴──┘
　　│　　　　　　　　　　　└────────┬──────────┘
　　│　　　　　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　↓キ　ソート終了│１０│２０│３０│４０│５０│６０│７０│８０│９０│
　　　　　　　　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘

手順の説明
　ソートの手順は、上図から明白でしょう。ア～エでデータの量を半分ずつに分割していく間に、区分のなかでソートしていれば、その区分はそのままにしておき、ソートされていない区分はさらに半分に分割していきます。
　それにより、エの段階で、すべての区分が区分内でソートされました。
　次に、分割と逆の順序で２つずつの区分をマージしていきます。オ～キのプロセスにより一つの配列になりました。

マージソートの計算量

　基本的な考え方は、対象となるデータの量（配列の大きさ）を小さくして、計算量を小さくすることにあります。
　単純にするために、ｎ＝２^m （ｍ＝log₂）のときを考えます。
・ｎ＝２（ｍ＝１）のとき
　　比較回数Ｃ₁＝１回
・ｎ＝４（ｍ＝２）のとき
　　データ個数２個の区分に分割すると、１区分をソートするための比較回数＝Ｃ₁＝１回
　　左右の２つがあるので、２×Ｃ₁＝２回
　　４個のデータマージするための比較回数＝ｎ－１回＝３回（＝２²－１）
　　全体の比較回数Ｃ₂＝２×Ｃ₁＋(ｎ－１)＝２×１＋３＝５回
・ｎ＝８（ｍ＝３）のとき
　　データ個数４個の区分に分割すると、一方をソートするための比較回数＝Ｃ₂＝５回
　　左右の２つがあるので、２×Ｃ₂＝１０回
　　８個のデータマージするための比較回数＝ｎ－１回＝７回（＝２³－１）
　　全体の比較回数Ｃ₃＝２×Ｃ₂＋(ｎ－１)＝２×５＋７＝１７回
これを一般化すると、
・ｎ＝２^ｍ のとき 　　Ｃ_m ＝２×Ｃ_m-1＋(ｎ－１)
　となります。
　プロセスは省略しますが、この式から、データ数ｎのときの比較回数は
　　　ｆ(ｎ) ＝ｎlog₂ｎ＋(ｎ－１)
　　　　　　　（ｎ＝２^ｍ とするとｆ(ｎ) ＝ｎ×ｍ＋(ｎ－１)　）
となります。
　ｎ＝２，４，８の場合では、
　　ｆ(２) ＝ｎ×ｍ－(ｎ－１)＝２×１－(２－１)＝　１　（＝Ｃ₁ )
　　ｆ(４) ＝ｎ×ｍ－(ｎ－１)＝４×２－(４－１)＝　５　（＝Ｃ₂ )
　　ｆ(８) ＝ｎ×ｍ－(ｎ－１)＝８×３－(８－１)＝１７　（＝Ｃ₃ )
となります。
　また、この式が正しいと仮定すると、Ｎ＝２ｎ、Ｍ＝ｍ＋１の場合は、
　　Ｃ_M ＝２×Ｃ_M-1 ＋(Ｎ－１)
の関係があるので、
　　ｆ(Ｎ) ＝ ２×ｆ(ｎ) ＋(Ｎ－１)
　　　　　 ＝ ２×｛ｎ×ｍ－(ｎ－１)｝＋(２ｎ－１)
　　　　　 ＝ ２ｎ×(ｍ＋１) － (２ｎ－１)
　　　　　 ＝ Ｎ×Ｍ－(Ｎ－１)
となり、上の式が成立するので、数学的帰納法により証明されます。
　また、計算量のオーダーＯ(n)は、
　　　　Ｏ(n)＝ｎlog(n)
となります。

プログラム

ア　function merge_sort(left, right) {
イ　　　var i, j , k, mid, w;
ウ　　　work = new Array(11);　　──作業領域が必要
エ　　　left = eval(left);
オ　　　right = eval(right);
カ　　　if (left < right) {　　　──分割して一つの要素になるまで行う
キ　　　　　if (right-left==1) {　　　　　┐
ク　　　　　　　if (a[left]>a[right]){　　│
ケ　　　　　　　　　w = a[left];　　　　　├左右が単一の要素の場合
コ　　　　　　　　　a[left] = a[right]; 　│　左＞右ならばスワップ
サ　　　　　　　　　a[right] = w; 　　　　│
シ　　　　　　　 }　　　　　　　　　　　　│
ス　　　　　} 　　　　　　　　　　　　　　┘
セ　　　　　else {　　　　　　　　　　　──もっと分割できる場合
ソ　　　　　　　mid = Math.floor((left+right)/2);　　　　┐
タ　　　　　　　merge_sort(left,mid);　　　　　　　　　　├左右２等分して再帰を行う
チ　　　　　　　merge_sort(mid+1,right); 　　　　　　　　┘
ツ　　　　　　　i = left;　　　　　　　　　　　　　　　　┐
テ　　　　　　　j = mid+1; 　　　　　　　　　　　　　　　│
ト　　　　　　　k = 1; 　　　　　　　　　　　　　　　　　│
ナ　　　　　　　while (i<=mid && j<=right) { 　　　　　　├配列ａを作業領域にコピー
ニ　　　　　　　　　if (a[i] < a[j])　work[k++]=a[i++];　│しながら左右をマージする
ヌ　　　　　　　　　else　　　　　　　work[k++]=a[j++];　│
ネ　　　　　　　}　　　　　　　　　　　　　　　　　　　　│
ノ　　　　　　　while (i<=mid)　　　　work[k++]=a[i++];　│
ハ　　　　　　　while (j<=right)　　　work[k++]=a[j++];　┘
ヒ　　　　　　　i = left;　　　　　　　　　　　　　　　　┐
フ　　　　　　　j = mid+1; 　　　　　　　　　　　　　　　│
ヘ　　　　　　　k = 1; 　　　　　　　　　　　　　　　　　├作業領域から配列に戻す
ホ　　　　　　　while (i<=mid)　　a[i++] = work[k++];　　│
マ　　　　　　　while (j<=right)　a[j++] = work[k++];　　┘
ミ　　　　　}
ム　　　}
メ　}

呼び出し側（メインプログラム）では、
　　　　merge_sort(1, n);
と指定します。
　ソートする配列ａ、そのサイズｎは共通領域で定義されているものとします。

マージソートと作業領域

マージソートは、分割するプロセスで一方の領域を作業領域（上のプログラムでの work）にコピーします。そのため、元の配列ａの半分（ｎ／２）の作業領域が必要になります。

クイックソート

全体のなかから、中間的な基準となる要素を１つ選び（ピボット－枢軸－という）、これより小さい要素と大きい要素の区分に分割します。さらに分割した２つの区分の中で分割を行います。これを繰り返してソートを行う方法です。

数値例

　ピボットより大の要素を探す　　　　　　ピボットより小の要素を探す
　　　　──────→　　　　　 ▽ 　　　　　　←──────
　　　┌───────────┬──┬───────────┐
　　　│３０　８０　７０　１０│５０│２０　４０　９０　６０│
　　　└───────────┴──┴───────────┘
　ア　　　　　　└─────スワップ────┘
　　　┌───────────┬──┬───────────┐
　　　│３０　４０　７０　１０│５０│２０　８０　９０　６０│
　　　└───────────┴──┴───────────┘
　イ　　　　　　▽　　└─スワップ──┘　　▽
　　　┌──┬──┬─────┐　　┌──┬──┬─────┐
　　　│３０│４０│２０　１０│５０│７０│８０│９０　６０│
　　　└──┴──┴─────┘　　└──┴──┴─────┘
　ウ　　　　　　└────┘　　　　　　　　　└────┘　　　カ
　　　┌──┬──┬─────┐　　┌──┬──┬─────┐
　　　│３０│１０│２０　４０│５０│７０│６０│９０　８０│
　　　└──┴──┴─────┘　　└──┴──┴─────┘
　エ　　　└─┘▽　　　　　　　　　　▽└─┘　　　　　　　　　キ
　　　┌──┬──┬─────┐　　┌──┬──┐
　　　│１０│３０│２０　４０│５０│６０│７０│９０　８０
　　　└──┴──┴─────┘　　└──┴──┘
　オ　　　　　▽└─┘　　　　　　　　　　　　　　▽　　　　　　ク
　　　┌──┬──┬─────┐　　　　　　　　┌──┬──┐
　　　│１０│２０│３０　４０│５０　６０　７０│９０│８０│
　　　└──┴──┴─────┘　　　　　　　　└──┴──┘
　　　　　　　　　　　　　　　　　　　　　　　　　　└─┘　　　ケ
　　　　　　　　　　　　　　　　　　　　　　　　┌──┬──┐
　　　　１０　２０　３０　４０　５０　６０　７０│８０│９０│
　　　　　　　　　　　　　　　　　　　　　　　　└──┴──┘
　　　　────────　ソートされている　───────→

• ピボットの選びかたにはいろいろありますが、ここでは、配列の中央（要素が偶数のときは中心の左側）の要素を選ぶことにします。
  図では、ピボットを▽で示しています。
• ピボットの左側にピボットより小さい要素、右側にピボットより小さい要素をもってくるのですが、左端からピボットより大の要素を探し、右端ピボットより小の要素を探します。
  アでは、８０と４０が見つかりますので、それをスワップします。イでは、７０と２０をスワップします。
  これで、左半分はピボットよりも小さい要素、右半分は大きな要素になりました。
• ウからオまでは、左半分（枠で囲まれた部分）を対象にします。４０がピボットになります。
  ウのように大小の要素をピボット自身も含むことにします。ウ～オのスワップが行われます。
• これにより、左半分はソートされました。右半分についても、カ～ケのようにしてソートされます。
  その結果、全体がソートされました。

マージソートとクイックソートの比較

• 計算量オーダーは同じ
  クイックソートでは、データの並びにより計算量が大きく変わります。アでは、たまたま配列の中点である要素が大きさの順でも中点であったため、左右の要素数が同じになりました。ところが、一方に多く偏ると（場合によっては、すべてが一方になることもある）、効率が悪くなります。
  　しかし、概念的には２等分したことになるので、計算量のオーダーはマージソートと同様に、Ｏ(ｎlog₂ｎ) になります。
• クイックソートのほうが効率がよい
  マージソートではマージが必要でした。また、元の配列と作業領域の間でのコピーが必要でした。クイックソートでは、それらが不要なため、計算量オーダーは同じですが、実際の効率はよくなります。
  また、作業領域が不要なことも優れています。
• 安定ソートではない
• マージソートでは、同じ値をもつ要素があるとき、元の配列順序を保ちつつスワップが行われますので安定ソートになります。ところが、クイックソートでは、ピボットより小さい（大きい）要素を探してスワップするときに、元の順序が崩れてしまいます。

プログラム

ア　function quick_sort(left, right) {
イ　　　var i, j;
ウ　　　var pivot;
エ　　　var w;
オ　　　left = eval(left);
カ　　　right = eval(right);
キ　　　i = left;　　　 /* 対象区分の左端 */
ク　　　j = right;　　　/* 対象区分の右端 */
ケ　　　pivot = a[Math.floor((i+j)/2)];　　/* 範囲の中点をピボットにする */
コ　　　while (i < j) {
サ　　　　　while( a[i] < pivot ) ++i;　/* ピボット以上の値が見つかるまで右へ */
シ　　　　　while( a[j] > pivot ) --j;　/* ピボット以下の値が見つかるまで左へ */
ス　　　　　if ( i < j ) {　　　　　　　/* 左＞ピボット＞右　なのでスワップ　*/
セ　　　　　　　w = a[i];
ソ　　　　　　　a[i] = a[j];
タ　　　　　　　a[j] = w;
チ　　　　　}
ツ　　　}
テ　　　if (left < i-1)　quick_sort(left, i-1);　　/* 左側についてクイックソートを再帰 */
ト　　　if (j+1 < right) quick_sort(j+1, right);　 /* 右側についてクイックソートを再帰 */
ナ　}

シェルソート

シェルソートは、ある一定距離だけ離れた要素同士でスワップを行います。それを繰返し、スワップが発生しなくなったら、、この距離を少しずつ縮めて距離が１になるまで行うとソートされています。
　距離ｈのとりかたは多様な考え方がありますが、データ数が比較的小さいときには、ｈ＝３ｋ＋１＜ｎ となる最大値から開始して、３ずつ減らしていく方法が広く行われています。

プログラム

ア　hmax = 3*Math.floor((n-1)/3) + 1;
イ　for (h=hmax; h>=1; h=h-3) { 　　　　　　　──┐
ウ　　　swap = 1; 　　　　　　　　　　　　　　　　├距離の幅ｈ
エ　　　while (swap == 1) { 　　　　　　──┐　　│を狭くする
オ　　　　　swap = 0; 　　　　　　　　　　　│
カ　　　　　for (i=1; i<=n-h; i++) {　┐　　├ｈおきで
キ　　　　　　　j = i + h;　　　　　　│　　│ソートされ
ク　　　　　　　if (a[i] > a[j]) {　　│　　│るまで行う
ケ　　　　　　　　　w = a[i]; 　　　　│　　│
コ　　　　　　　　　a[i] = a[j];　　　│
シ　　　　　　　　　a[j] = w; 　　　　├ｈだけ離れた
ス　　　　　　　　　swap = 1; 　　　　│要素間で比較
セ　　　　　　　} 　　　　　　　　　　│
ソ　　　　　} 　　　　　　　　　　──┘　　│　　│
タ　　　} 　　　　　　　　　　　　　　　──┘　　│
チ　} 　　　　　　　　　　　　　　　　　　　　──┘

数値例

距離ｈ＝７
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　　│３０│８０│７０│１０│５０│２０│４０│９０│６０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘
　ア　　└①─┼─────────────────┘
　　　　　　　└②───────────────────┘
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　①│３０│　　│　　│　　│　　│　　│　　│９０│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　②│　　│６０←─────────────────→８０│スワップ発生
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　　│３０│６０│７０│１０│５０│２０│４０│９０│８０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘
　イ　　└①─┼─────────────────┘
　　　　　　　└②───────────────────┘
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　①│３０│　　│　　│　　│　　│　　│　　│９０│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　②│　　│６０│　　│　　│　　│　　│　　│　　│８０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘スワップ発生せず
距離ｈ＝４
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　　│３０│６０│７０│１０│５０│２０│４０│９０│８０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘
　　　　└①─┼──┼──┼──┘│　│　　│　　│　　│
　　　　　　　└②─┼──┼───┼─┘　　│　　│　　│
　ウ　　　　　　　　└③─┼───┼────┘　　│　　│
　　　　　　　　　　　　　└④──┼───────┘　　│
　　　　　　　　　　　　　　　　　└⑤─────────┘
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　①│３０│　　│　　│　　│５０│　　│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　②│　　│２０←────────→６０│　　│　　│　　│スワップ発生
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　③│　　│　　│４０←────────→７０│　　│　　│スワップ発生
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　④│　　│　　│　　│１０│　　│　　│　　│９０│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑤│　　│　　│　　│　　│５０│　　│　　│　　│８０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　　│３０│２０│４０│１０│５０│６０│７０│９０│８０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘
　　　　└①─┼──┼──┼──┘│　│　　│　　│　　│
　　　　　　　└②─┼──┼───┼─┘　　│　　│　　│
　エ　　　　　　　　└③─┼───┼────┘　　│　　│
　　　　　　　　　　　　　└④──┼───────┘　　│
　　　　　　　　　　　　　　　　　└⑤─────────┘
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　①│３０│　　│　　│　　│５０│　　│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　②│　　│２０│　　│　　│　　│６０│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　③│　　│　　│４０│　　│　　│　　│７０│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　④│　　│　　│　　│１０│　　│　　│　　│９０│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑤│　　│　　│　　│　　│５０│　　│　　│　　│８０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘スワップ発生せず
距離ｈ＝１
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　　│３０│２０│４０│１０│５０│６０│７０│９０│８０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘
　オ　　　└①┘└②┘└③┘└④┘└⑤┘└⑥┘└⑦┘└⑧┘
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　①│２０⇔３０│　　│　　│　　│　　│　　│　　│　　│スワップ発生
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　②│　　│３０│４０│　　│　　│　　│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　③│　　│　　│１０⇔４０│　　│　　│　　│　　│　　│スワップ発生
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　④│　　│　　│　　│４０│５０│　　│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑤│　　│　　│　　│　　│５０│６０│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑥│　　│　　│　　│　　│　　│６０│７０│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑦│　　│　　│　　│　　│　　│　　│７０│９０│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑧│　　│　　│　　│　　│　　│　　│　　│８０⇔９０│スワップ発生
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　　│２０│３０│１０│４０│５０│６０│７０│８０│９０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘
　カ　　　└①┘└②┘└③┘└④┘└⑤┘└⑥┘└⑦┘└⑧┘
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　①│２０│３０│　　│　　│　　│　　│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　②│　　│１０⇔３０│　　│　　│　　│　　│　　│　　│スワップ発生
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　③│　　│　　│３０│４０│　　│　　│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　④│　　│　　│　　│４０│６０│　　│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑤│　　│　　│　　│　　│５０│６０│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑥│　　│　　│　　│　　│　　│６０│７０│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑦│　　│　　│　　│　　│　　│　　│７０│８０│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑧│　　│　　│　　│　　│　　│　　│　　│８０│９０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　　│２０│１０│３０│４０│５０│６０│７０│８０│９０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘
　キ　　　└①┘└②┘└③┘└④┘└⑤┘└⑥┘└⑦┘└⑧┘
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　①│１０⇔２０│　　│　　│　　│　　│　　│　　│　　│スワップ発生
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　②│　　│２０│３０│　　│　　│　　│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　③│　　│　　│３０│４０│　　│　　│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　④│　　│　　│　　│４０│５０│　　│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑤│　　│　　│　　│　　│５０│６０│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑥│　　│　　│　　│　　│　　│６０│７０│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑦│　　│　　│　　│　　│　　│　　│７０│８０│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑧│　　│　　│　　│　　│　　│　　│　　│８０│９０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　　│１０│２０│３０│４０│５０│６０│８０│８０│９０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘
　ク　　　└①┘└②┘└③┘└④┘└⑤┘└⑥┘└⑦┘└⑧┘
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　①│１０│２０│　　│　　│　　│　　│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　②│　　│２０│３０│　　│　　│　　│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　③│　　│　　│３０│４０│　　│　　│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　④│　　│　　│　　│４０│５０│　　│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑤│　　│　　│　　│　　│５０│６０│　　│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑥│　　│　　│　　│　　│　　│６０│７０│　　│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑦│　　│　　│　　│　　│　　│　　│７０│８０│　　│
　　　├──┼──┼──┼──┼──┼──┼──┼──┼──┤
　　⑧│　　│　　│　　│　　│　　│　　│　　│８０│９０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘スワップ発生せず
終了
　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　　│１０│２０│３０│４０│５０│６０│８０│８０│９０│
　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┘

距離ｈを３ｋ＋１のルールにより、ｈ＝７、４、１の順で行いました。
　アではｈ＝７です。①で、a[1]＝３０ と a[1+7]＝a[8]＝９０ の比較をしますが、a[1]＜a[8] なので、そのままになります。②で、a[2]＝８０ と a[9]＝６０ の比較をしますが、a[2]＞a[9] なので、スワップします。
　スワップが行われたので、ｈ＝７を繰り返すためイを行います。イではスワップが行われなかったので、距離ｈを狭くしてｈ＝４とし、ウを行います。
　このような手順により、ｈ＝１でスワップが行われなくなった（ク）でソートが終了します。

計算オーダー

シェルソートの計算量は、ｈの取り方により大きく変わります。しかも、最適なｈは元データの並び方により変化します。そのため、非常に高速になる場合と、バブルソートとあまり変わらなくなる場合もあります。だいたいＯ(ｎ^1.2）程度のオーダーだといわれています。

ヒープソート

ヒープソートとは、配列から２分木を作り、それを 親＜左の子＜右の子 の順序木にするように修正することにより、ソートする方法です。

数値例（ステップ１：２本木の作成）

９個のデータがあるので、完全２分木はアの構造になります。ノード番号（①～⑨）には次の特徴があります。
　　　同じ階層のノードは続き番号になっている。
　　　親のノード番号をｉすると、左の子のノード番号ｊは、ｊ＝２×ｉ である。（右の子はｊ＋１）
これに、a[9]→a[8]→…→a[1]の順に、次の規則によりノードに割り付けます。
　　ノードが葉（枝をもたない）場合（⑨から⑤まで）
　　　　要素番号をそのままノード番号として割り付ける。
　　ノードが枝をもつ場合
　　　　子よりも大ならば、
　　　　　　そのままノード番号として割り付ける。
　　　　子よりも小ならば、
　　　　　　子を親に移す。それに関連する部分も親＞子となるようにする。
　　　　　　動かした最期のノード（最下段の子のノード）に割り付ける。
　（親＞子として２分木を作るのは、「昇順」にソートすることと矛盾しているように見えますが、これでよいのです）

• ア：⑨から⑤までは葉なので、要素番号をそのままノード番号として割り付ける。
• イ：a[4]=10 を④に割り付けようとするが、子の⑧（a[8]=90）のほうが大きいので、⑧を④に移動して（a[4]=90として）、１０を⑧に割り付ける（a[8]=10とする）→ウ
• ウ：a[3]=70 を③に割り付けようとする。これは、子の⑥、⑦より大なので、そのまま（a[3]=70）とする→エ
• エ：a[2]=80 を②に割り付けようとするが、子の④（a[4]=90）のほうが大きいので、④を②に移動（a[4]=90）する。８０を④に割り付け（a[4]=80）ても、親（④）＞子（⑧、⑨）の関係が成立するので、８０を④に割り付ける（a[4]=80）→オ
• オ：a[1]=30 を①に割り付けようとするが、子の②（a[2]=90）のほうが大きいので、④を②に移動（a[4]=90）する。３０を②に割り付け（a[2]=30）ようとするが、②よりも、その子である⑨（a[9]=60）のほうが大きいので、⑨を④に移動して（a[4]=60）、３０を⑨に割り付ける（a[9]=30）

これにより、すべてのノードに要素が入り、２分木が作成されました（カ）。

数値例（ステップ２：２本木の修正）

昇順にソートする（順序木－下図のセ）にするには、
　　条件１　要素の値が、親＜左の子＜右の子 にする（最小値がルート①になる）。 　　条件２　ノードが小さいほうが値が小さくなるようにする。 必要があります。
　カでは、親＞子の関係（１の逆）が成立しています。最大値がルート①にあるのですから、それをa[9]（ノード⑨へ移動）にすることが考えられます。そして、「２分木の順序を変更」すれば、次の最大値がルート①になるので、それをa[8]（ノード⑨へ移動）するというプロセスにすればよいことになります（これがステップ１で、親＞子にした理由です）。
　条件１、２を満足するように「２分木の順序を変更」するには、次のようにします。
　　　対象となるノードｋの値をＷに保存しておく（w←a[k]） 　　　ルート①をkに移す（a[k]←a[1]） 　　　子の

• カ：ルート①＝９０を⑨に移すには、⑨＝３０の親④を②に移すことが必要で、さらに②を①に移す必要がある。
  すなわち、②→①、④→②、⑨→①として、①→⑨の移動をする。以降⑨は検討の対象から外すことができる。→キ
• キ：①→⑧とするとき、現在の子⑧＜親④なので、親④への移動は必要はない。
  それで、条件２を満足させるために、親④の次（降順なので③になる）の子（⑥と⑦）と⑧を比較する。降順で比較するので、まず⑦との比較になる。⑧＜⑦なので、⑧を⑦に移動させたい。そのためには、⑦→③、③→①の移動が必要になる。
  すなわち、③→①、⑦→③、⑧→⑦、①→⑧の移動をする。→ク
• ク：①→⑦とするとき、子⑦＜親③なので、③の子（⑤と⑥）との比較になり、⑦＞⑧を比較する。降順で比較するので、まず⑦との比較になる。⑦＜⑤なので移動が必要。そのためには、⑤→②→①の移動が必要になる。
  すなわち、②→①、⑤→②、⑦→⑤、①→⑦の移動をする。→ケ

同様にケ～スを行うことにより、セになります。
①→②→…→⑨とたどれば、昇順になっていることがわかります。すなわち、a[1]＜a[2]＜…＜a[9] になり、ソートが終了したのです。

プログラム

　２分木を作成する
ア　for (k=n; k>=1; k--) {　　──葉のほうからデータを割り付ける
イ　　　i = k;　　　　　　　　　ｉ、ｊはノード番号
ウ　　　w = a[i];　　　　　　　　（親＝ｉ、左の子＝ｊ、右の子＝ｊ＋１）
エ　　　while ((j = i*2) <= n) {　　　　　　　　──┐
オ　　　　　if ((j<=n-1) && (a[j] < a[j+1])) j++; 　├親になる（葉ではない）
カ　　　　　if ( w >= a[j]) break;　　　　　　　　　│ノードのとき
キ　　　　　a[i] = a[j];　　　　　　　　　　　　　　│　親＞子になるように
ク　　　　　i = j;　　　　　　　　　　　　　　　　　│　必要ならばスワップ
ケ　　　} 　　　　　　　　　　　　　　　　　　　──┘
コ　　　a[i] = w;　　──ノードが葉のときは、ノード番号＝要素番号として入れる
サ　}　　　　　　　　　　葉ではないときは、上のスワップにより得た親のノードに入れる
　親＜左の子＜右の子　になるように修正する
シ　k = n;
ス　while (k >= 2) {
セ　　　w = a[k];
ソ　　　a[k] = a[1];　　　──a[1]＝ルート（本来ならば最小値）
タ　　　k--;　　　　　　　──⑨→⑧→…降順で行う
チ　　　i = 1;
ツ　　　while ((j=i*2) <= k) {　　　　　　　　　──┐
テ　　　　　if ((j < k) && (a[j] < a[j+1])) j++;　　│
ト　　　　　if (w >= a[j]) break; 　　　　　　　　　│
ナ　　　　　a[i] = a[j];　　　　　　　　　　　　　　├数値例での解説参照
ニ　　　　　i = j;　　　　　　　　　　　　　　　　　│
ヌ　　　} 　　　　　　　　　　　　　　　　　　　　　│
ネ　　　a[i] = w; 　　　　　　　　　　　　　　　──┘
ノ　}

計算量オーダー等

処理が複雑なのでわかりにくいのですが、２分木であることから、計算量オーダーは Ｏ(ｎlog₂ｎ) であることが推察できましょう。
　大小の比較順序が、要素順序になっていないので、安定ソートではありません。

計算プログラム