インプレースマージソートの理解

Question

マージソートのインプレースバージョンを理解するのが難しいです。

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

    while (il < left.length &#038;&#038; 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)); 
} 


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; 
} 

のparamsの前に0とitems.lengthを添加する目的は何ですか？私はitems.splice.applyが何をしているのか理解できませんが、コンソールにいくつかの例を記録すると、それはちょうどparamsにシフトされていなかったものを削除するようです。これの理由は何ですか？

Answer 1

TLDR：itemsの内容をソート済みのバージョンに置き換えます。

---

Array.prototype.splicethe following signatureがあります

array.splice(start, deleteCount[, item1[, item2[, ...]]]) 

それはインデックスstartから始まるdeleteCount項目を削除し、提供項目に置き換えます。

items.splice.apply(items, params)は、paramsから取られたパラメータでitems.splice(...)を実行します。 params.unshift(0, items.length)後、paramsは

[0, items.length, sortedItem1, sortedItem2, ...] 

あるので、呼び出しはitems.lengthアイテムインデックス0（それらのように全て）から出発し、ソート順の項目に置き換える削除、items.splice(0, items.length, sortedItem1, sortedItem2, ...)を実行します。