問題描述
透過函式將陣列中的數值加以排序。
前置知識：Merge Sort
Merge Sort 的演算法主要包含兩個部分：
1. 將陣列對半拆分
Merge Sort 的第一步是要將陣列兩兩對半拆分，直到拆到每個陣列只剩一個元素：
[3, 20, 8, 5, 1, 12, 17, 2]
[3, 20, 8, 5], [1, 12, 17, 2]
[3, 20], [8, 5], [1, 12], [17, 2]
[3], [20], [8], [5], [1], [12], [17], [2]
2.將陣列排序後加以合併
我們把上面拆分好的陣列，兩兩一組開始進行排序，每次排序時都是取該陣列的第一個元素進行比較：
[3], [20], [8], [5], [1], [12], [17], [2]
[3, 20], [5, 8], [1, 12], [2, 17]
[3, 5, 8, 20], [1, 2, 12, 17]
[ 1, 2, 3, 5, 8, 12, 17, 20 ]
兩兩比較後排序的方式可以參考下圖，每次比較都是取各陣列的第一個元素來進行比較：
整個合併排序法如下圖所示：
因此我們一共需要兩個函式，並且一樣會透過遞回函式的方式來處理：
function mergeSort (arr) {
}
function sortBeforeMerge (arr1, arr2) {
}
Merge Sort 這個演算法我覺得稍微有一點點小小複雜，非常需要圖像化來幫助思考，但我們可以先看 code ，看完之後會更瞭解它實際上的運作方式。
演算法實做
1. 將陣列進行對半切分
首先要將傳進來的陣列進行對半切分，這裡可以透過 Array.prototype.slice 來進行：
function mergeSort (arr) {
let middleIndex = Math.floor(arr.length / 2)
let firstHalf = arr.slice(0, middleIndex)
let secondHalf = arr.slice(middleIndex)
}
2. 將兩組各自已經排序過的陣列以 merge sort 的方式合併
首先透過 while 迴圈，當傳入的兩組 已經各自排序過的 的陣列 arr1 和 arr2 都沒有空陣列的情況下，選出兩陣列中當時的第一個元速進行比較，把比較小的先放入 sortedArr 中：
function sortBeforeMerge (arr1, arr2) {
let sortedArr = []
while (arr1.length && arr2.length) {
let minElement = (arr1[0] < arr2[0]) ? arr1.shift() : arr2.shift()
sortedArr.push(minElement)
}
}
Array.prototype.shift() 可以把移除陣列中的第一個元素，並把它存出來。
經過 while 迴圈後，我們會得到一組已經經過 merge sort 方式排序好的陣列；另外，while 迴圈終止的條件是只要 arr1 或 arr2 其中一組為空陣列時就會停止，因此這時候 arr1 或 arr2 其中有一組還不是空陣列，我們要把不為空陣列的陣列透過 Array.prototype.concat 連接到 sortedArr 後面。
由於我們傳進 sortBeforeMerge 這個函式的陣列是已經經過排序的，因此，可以確定透過 concat 連結好的陣列，其數值也會是由小到大的：
function sortBeforeMerge (arr1, arr2) {
let sortedArr = []
while (arr1.length && arr2.length) {
}
sortedArr = arr1.length ? sortedArr.concat(arr1) : sortedArr.concat(arr2)
return sortedArr
}
3. 結合遞回函式
最後我們要把 mergeSort 這個函式結合遞回的概念，在使用遞回函式時，一定要記得設定終止條件：
function mergeSort (arr) {
if (arr.length <= 1) {
return arr
}
return sortBeforeMerge(mergeSort(firstHalf), mergeSort(secondHalf))
}
完整程式碼
function mergeSort (arr) {
if (arr.length <= 1) {
return arr
}
let middleIndex = Math.floor(arr.length / 2)
let firstHalf = arr.slice(0, middleIndex)
let secondHalf = arr.slice(middleIndex)
return sortBeforeMerge(mergeSort(firstHalf), mergeSort(secondHalf))
}
function sortBeforeMerge (arr1, arr2) {
let sortedArr = []
while (arr1.length && arr2.length) {
let minElement = (arr1[0] < arr2[0]) ? arr1.shift() : arr2.shift()
sortedArr.push(minElement)
}
sortedArr = arr1.length ? sortedArr.concat(arr1) : sortedArr.concat(arr2)
return sortedArr
}
console.log(mergeSort([3, 20, 8, 5, 1, 12, 17, 2]))
圖像化思考
上面這個情況可能會有點難想像實際上的遞回是怎麼執行的，假設我們現在執行函式：
mergeSort([4, 3, 2, 1])
它實際上會先將陣列拆成 [4, 3] 和 [2, 1]，接著
return sortBeforeMerge(mergeSort[4, 3], mergeSort[2, 1])
這時候遞回函式就需要先去計算出 mergeSort[4, 3] 和 mergeSort[2, 1] 的值。
以 mergeSort[4, 3] 為例，它則是會先把陣列拆成 [4], [3]，接著 return sortBeforeMerge([4], [3]) ，在經過 sortBeforeMerge 的函式時，它會取這兩個陣列當時的第一個元素比較大小，最後會回傳 [3, 4]。
同理， mergeSort[2, 1] 在經過 sortBeforeMerge([2], [1]) 之後，會回傳 [1, 2]。
如下圖所示：
因此一開始的：
return sortBeforeMerge(mergeSort[4, 3], mergeSort[2, 1])
便會變成：
return sortBeforeMerge([3, 4], [1, 2])
最後便會得到 [1, 2, 3, 4]。
如下圖所示：
資料來源
