mergemd-compressor
マージ（merge）とは、「併合する」「合併する」という意味を指す。

与えられた数列を2つの部分列に分解し、各部分列に対して再帰的に整列アルゴリズムを適用するので「再帰的数列」に分類される。


１ 》マージソート図解

（昇順に並び替える）
  1. 与えられた数列を2分割する（left,mid,right位置を決める）
  2. 各部分列に対して再帰的にマージソートを適用
  3. 整列済みの部分列を求める
  4. これらの部分列をマージする

具体例を次に示す
marge1-compressor
  1. left（左端）,mid（分割要素）,right（右端）の配列要素を決定、再帰的に2分割を繰り返す
  2. 整列部の大きさが1になるまで繰り返し、大きさ１の数列をマージして大きさ2の整列された数列を求め、同様に大きさ2の数列をマージして大きさ4の整列された数列を求める。
  3. このような操作をすべての部分列をマージするまで繰り返す。

【マージ手順】
整列済みリストAと整列済みリストBをマージしてリストCにまとめる。
  1. リストAとリストBの先頭要素を比較
  2. 小さいほうをリストから削除しリストCの末尾に追加
  3. リストA、または、リストBの要素がなくなるまで1，2を繰り返す
  4. 残りの要素をリストCに追加

特徴


  • 整列対象のデータが追加される状況においても、すでに整列済みのデータを用いて処理を再開できる
　　→オンラインアルゴリズム

  • 同一キーを持つ要素の順序がソート前後で維持される
　　→安定なソート


計算量


データ数をNとすると

分割回数　logN

マージソートのオーダー　O(NlogN)


２ 》マージソートプログラム


配列の中身を昇順に並び替える

function mergeSort(numbers,temp,array_size)
{
    m_sort(numbers,temp,0,array_size-1);
}

function m_sort(numbers,temp,left,right)
{
    var mid;
    if(right > left)
    {
        mid = parseInt((right+left)/2); /* 配列を分割する位置 */
        m_sort(numbers,temp,left,mid);
        m_sort(numbers,temp,mid+1,right);

        merge(numbers,temp,left,mid+1,right);
    }
}

function merge(numbers, temp, left, mid, right)
{
    var left_end, num_elements, tmp_pos;

    left_end = mid-1;
    tmp_pos = left;
    num_elements = right-left+1; /* 配列の要素数 */

    //2つのリストに要素が残っている
    while((left <= left_end) && (mid <= right))
    {
        if(numbers[left] <= numbers[mid])
        {
            temp[tmp_pos] = numbers[left];
            tmp_pos = tmp_pos+1;
            left = left+1;
        }
        else
        {
            temp[tmp_pos] = numbers[mid];
            tmp_pos = tmp_pos+1;
            mid = mid+1;
        }
    }

    //左側のリスト
    while(left <= left_end)
    {
        temp[tmp_pos] = numbers[left];
        left = left+1;
        tmp_pos = tmp_pos+1;
    }
    //右側のリスト
    while(mid <= right)
    {
        temp[tmp_pos] = numbers[mid];
        mid = mid+1;
        tmp_pos = tmp_pos+1;
    }

    //昇順に整列させリストにまとめる
    for(var i=0;i <= num_elements;i++)
    {
        numbers[right] = temp[right];
        right = right-1;
    }
}

//ここから開始
var h=[6,3,8,4,5,1,2,9,7,0];
document.write("整列前：");
for(var i=0;i < h.length;i++)
{
    document.write(h[i]+" ");
}
document.write("<br>");

//配列を作成
var temp = Array(); 
//マージソート
mergeSort(h,temp,h.length);

document.write("整列後：");
for(var i=0;i < h.length;i++)
{
    document.write(h[i]+" ");
}

【実行結果】
整列前：6 3 8 4 5 1 2 9 7 0
整列後：0 1 2 3 4 5 6 7 8 9

３ 》その他ソート

  1. 選択ソート
  2. バブルソート
  3. 挿入ソート
  4. マージソート
  5. シェルソート
  6. ヒープソート
  7. クイックソート