Javascript順序付けアルゴリズムの統合順序付け（並べ替え）の2つの例

正規化順序付け（Merge sort）は、正規化動作において確立された効率的な並べ替えアルゴリズムである。このアルゴリズムはディヴィッド・アンド・コンクラーを用いた非常に典型的な応用である。
正規化（Merge）順序付け法は、2つ（または2つ以上）の順序テーブルを新たな順序テーブルに結合することであり、すなわち、順序付けされているシーケンスをいくつかのサブシーケンスに分け、各サブシーケンスは順序付けされている。そして、秩序のあるサブシーケンスを統合して、秩序のあるシーケンスにします。
正規化順序付けは、正規化動作において確立された効率的な並べ替えアルゴリズムである。このアルゴリズムはディヴィッド・アンド・コンクラーを用いた非常に典型的な応用である。既存の順序のサブシーケンスを統合し、完全に秩序化されたシーケンスを得る。すなわち、各サブシーケンスを先に秩序化し、サブシーケンスセグメント間を秩序化させる。二つの順序表を一つの順序表に統合すれば、2－路帰合と呼ばれます。
まとめて操作する過程は以下の通りです。
1.統合されたシーケンスを格納するための空間の大きさを2つの並べ替え済みシーケンスの和にします。2つのポインタを設定し、最初の位置はそれぞれ2つの並べ替えられたシーケンスの開始位置とします。3.2つのポインタが指す要素を比較し、比較的小さい要素を結合空間に配置します。ポインタを次の位置に移動します。ステップ3を繰り返します。ポインタがシーケンスの最後に達するまで、残りのすべての要素を連結シーケンスの最後に直接コピーします。
例1:

/**
 *     (merge)，      ，                       。
 *             。
 *
 *          ：
 *
 * 1、    ，               ，             
 * 2、      ，                    
 * 3、            ，               ，          
 * 4、    3           
 * 5、                      
 *
 */

function mergeSort(items) {
    if (items.length < 2) {
        return items;
    }

    var middle = Math.floor(items.length / 2),
        left = items.slice(0, middle),
        right = items.slice(middle),
        params = merge(mergeSort(left), mergeSort(right));

    params.unshift(0, items.length);
    items.splice.apply(items, params);

    return items;

    function merge(left, right) {
        var result = [],
            il = 0,
            ir = 0;

        while (il < left.length && ir < right.length) {
            if (left[il] < right[ir]) {
                result.push(left[il++]);
            } else {
                result.push(right[ir++]);
            }
        }
        return result.concat(left.slice(il)) .concat(right.slice(ir));
    }
}

// test
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];

mergeSort(arr);

例2:

<script type="text/javascript">
//document.write("----------    -----            ,      nlogn------<br />");
//var array = new Array(12, 25, 32, 16, 18, 27, 59, 69, 36);
var count = 0;
//          
//mSort(array, array, 0, array.length - 1);
//source   
//dest    
//s    
//t    
function mSort(source, dest, s, t) {
 var result = "";
 var m; //    

 var dest2 = new Array();
 if (s == t) {
   dest[s] = source[s];
    }
  else {
       m = Math.floor((s + t) / 2);
     mSort(source, dest2, s, m);
      mSort(source, dest2, m+1 , t);
       merge(dest2, dest, s, m, t);
      /*      */
      result += "<br /> " + ++count + "       :";
   for (var n = 0; n < dest.length; n++) {
          result+= array[n] + ",";
        }
     /*        */
 }
 return result;
}

/*        */
//                
//source   
//dest      
//s     
//m       
//n   
function merge(source, dest, s, m, n) {
 for (var j = m+1, k = s; j <= n && s <= m; k++) {
   if (source[s] < source[j]) {
       dest[k] = source[s++];
     }
    else {
         dest[k] = source[j++];
       }
  }

 //              dest   
   if (s <= m) {
        for (var l = 0; l <= m - s; l++) {
         dest[k + l] = source[s+l];
      }
  }
 if (j <= n) {
      for (var l = 0; l <= n - j; l++) {
       dest[k + l] = source[j+l];
       }
 }
}
//document.write("<br /><br />")
</script>