JavaScript 中的計算機科學：歸併排序
合併排序可以說是您在計算機科學中學習的第一個有用的排序算法。合併排序的複雜度為 O(n log n)，使其成為可用的更有效的排序算法之一。此外，歸併排序是一種穩定的排序（就像插入排序一樣），因此等價項的相對順序在排序前後保持不變。這些優勢就是為什麼 Firefox 和 Safari 使用歸併排序來實現 Array.prototype.sort() .
歸併排序的算法基於這樣一種思想，即合併兩個已排序的列表比處理單個未排序的列表更容易。為此，合併排序首先創建 n 個單項列表，其中 n 是原始列表中要排序的項目總數。然後，算法繼續將這些項目列表組合回單個排序列表。
合併兩個已經排序的列表是一個非常簡單的算法。假設您有兩個列表，列表 A 和列表 B。您從每個列表的前面開始並比較這兩個值。將較小的值插入結果數組。所以假設較小的值來自列表A；該值被放入結果數組中。接下來，將列表 A 中的第二個值與列表 B 中的第一個值進行比較。再一次，將兩個值中較小的一個放入結果列表中。因此，如果較小的值現在來自列表 B，那麼下一步是將列表 A 中的第二項與列表 B 中的第二項進行比較。代碼如下：
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));
}</code>
這個函數合併兩個數組，left 和 right . il 變量跟踪要比較 left 的索引 而 ir right 也一樣 .每次添加一個數組中的值時，其對應的索引變量就會遞增。一旦其中一個數組用完，剩餘的值就會使用 concat() 添加到結果數組的末尾 .
merge() 函數非常簡單，但現在您需要組合兩個排序列表。如前所述，這是通過將數組拆分為多個單項列表，然後系統地組合這些列表來完成的。使用遞歸算法很容易做到這一點：
function mergeSort(items){
// Terminal case: 0 or 1 item arrays don't need sorting
if (items.length < 2) {
return items;
}
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}</code>
首先要注意的是包含零個或一個項目的數組的終端情況。這些數組不需要排序，可以按原樣返回。對於具有兩個或多個值的數組，首先將數組分成兩半，創建 left 和 right 數組。然後將這些數組中的每一個傳回 mergeSort() 將結果傳遞到 merge() .所以算法是先對數組的左半邊排序，再對數組的右半邊排序，然後合併結果。通過這個遞歸，最終你會到達一個點，將兩個單值數組合併。
這種合併排序的實現返回一個與傳入的數組不同的數組（這不是“就地”排序）。如果您想創建就地排序，那麼您可以隨時清空原始數組並用排序後的項目重新填充它：
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));
// Add the arguments to replace everything between 0 and last item in the array
params.unshift(0, items.length);
items.splice.apply(items, params);
return items;
}</code>
這個版本的mergeSort() 函數將排序結果存儲在名為 params 的變量中 .替換數組中的項目的最佳方法是使用 splice() 方法，它接受兩個或多個參數。第一個參數是要替換的第一個值的索引，第二個參數是要替換的值的數量。每個後續參數都是要插入該位置的值。由於無法將值數組傳遞到 splice() , 你需要使用 apply() 並傳入前兩個參數和排序數組。所以，``和items.length 使用 unshift() 添加到數組的前面 這樣 apply() 可與 splice() 一起使用 .然後，返回原始數組。
歸併排序可能是您將學習的最有用的排序算法，因為它具有良好的性能和易於實現的特點。與我介紹的其他排序算法一樣，最好還是從原生 Array.prototype.sort() 開始 在嘗試自己實現其他算法之前。在大多數情況下，本機方法會做正確的事情並提供最快的實現。但是請注意，並非所有實現都使用穩定的排序算法。如果使用穩定的排序算法對您很重要，那麼您需要自己實現一個。
您可以獲得兩個版本的 mergeSort() 來自我的 GitHub 項目，JavaScript 中的計算機科學。
