JavaScriptでマージソート

配列のマージソートを、難しいテクニックを使わないスタンダードな書き方でのサンプル。

function merge_sort( a , start , end ) {
   if ( start + 1 == end ) {
      // a[start]の1件だけなので並び替える必用なし
   } else {
      // 真ん中
      var mid = Math.floor( (start + end) / 2 ) ;
      // 左半分を並べ替え
      merge_sort( a , start , mid ) ;
      // 右半分を並べ替え
      merge_sort( a , mid , end ) ;

      // 2つの山をマージする。
      var temp = new Array() ;          // マージ結果の一時的保存用
      var lt = start ;                  // 左の山の先頭
      var rt = mid ;                    // 右の山の先頭
      // ここがまだダサい。
      for( i = 0 ; i < end - start ; i++ ) {
         var w ;
         if ( lt >= mid ) {        // 左の山が空、右の山から取り出す
            w = a[ rt ] ;
            rt++ ;
         } else if ( rt >= end ) { // 右の山が空、左の山から取り出す
            w = a[ lt ] ;
            lt++ ;
         } else if ( a[lt] > a[rt] ) {  // 左の山から取り出す
            w = a[ lt ] ;
            lt++ ;
         } else {                       // 右の山から取り出す
            w = a[ rt ] ;
            rt++ ;
         }
         temp[ i ] = w ;
      }
      // マージした結果を、a[]のstart..endに戻す
      for( var i = 0 ; i < end - start ; i++ ) {
         a[ start + i ] = temp[ i ] ;
         console.log( "a["+(start+i)+"]="+a[start+i]) ;
      }
   }
}

array = new Array( 11 , 45 , 22 , 33 , 77 , 88 , 44 , 55 ) ;
merge_sort( array , 0 , array.length ) ;
for( var i = 0 ; i < array.length ; i++ )
   console.log( "a["+i+"]=" + array[i] ) ;