---

マージソート

---

N個のデータが，配列 a[0]〜 a[N-1]に格納されているとする．

マージソート：

作業用に配列 w[] を使用する場合

1. リスト(a[0] 〜 a[N-1]) を半分に別けて，
2. 左をマージソートする
3. 右をマージソートする
4. 両者をソートしながら統合(マージ)する

      marge_sort(a, left, right) {
         center = (left+right+1)/2;
         if(left < center-1) marge_sort(a, left, center-1);
         if(center < right)  marge_sort(a, center, right);
	 (a[left]〜a[center-1])と(a[center]〜a[right])を統合する;
      }

(a[left]〜a[center-1])と(a[center]〜a[right])を統合する ：

1. a[left]〜a[right]を作業用の配列 w[left]〜w[right] にコピーする
2. l ← left,  r ← center
3. for( p = left; p <= right; p++)
   • w[l] と w[r] を比較する
     w[l] <= w[r] ならば，w[l] を取り出す以下の操作を行う

                 a[p] = w[l];
                 if( l < center-1 ) l++;
                 else w[l] = w[right]+1;
     

     w[l] > w[r] ならば，w[r]を取り出す以下の操作を行う

                 a[p] = w[r];
                 if( r > right) r++;
                 else w[r] = w[center-1]+1;
     

(a[left]〜a[c-1])と(a[c]〜a[right])をマージする

      do {
         if(a[left] > a[c]) {
            t = a[c];
            for(p=c; p>left; p--) {
               a[p] = a[p-1];
            }
	    c++;
	    a[left] = t;
         }
	 left++;
      } while( (l < r) & (r <= right) );