參考鏈接
歸并排序是建立在歸并操作上的一種有效的排序算法助泽，該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用大猛。將已有序的子序列合并痪蝇，得到完全有序的序列急膀；即先使每個(gè)子序列有序峦阁，再使子序列段間有序钝腺。
基本思想
歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表抛姑，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的艳狐。然后再把有序子序列合并為整體有序序列途戒。
初始關(guān)鍵字 49 38 65 97 76 13 27
第一趟歸并 (38 49) (65 97) (13 76) 27
第二趟歸并 (38 49 65 97) (13 27 76)
第三趟歸并 (13 27 38 49 65 76 97)
將待排序序列R[0...n-1]看成是n個(gè)長(zhǎng)度為1的有序序列，將相鄰的有序表成對(duì)歸并僵驰，得到n/2個(gè)長(zhǎng)度為2的有序表喷斋；將這些有序序列再次歸并唁毒，得到n/4個(gè)長(zhǎng)度為4的有序序列；如此反復(fù)進(jìn)行下去星爪，最后得到一個(gè)長(zhǎng)度為n的有序序列浆西。
綜上可知，歸并排序其實(shí)要做兩件事：
（1）“分解”——將序列每次折半劃分顽腾。
（2）“合并”——將劃分后的序列段兩兩合并后排序近零。
算法的實(shí)現(xiàn)
extension Array where Element: Comparable {
mutating func mergeSort() {
var temp = self
func msort(left: Int, right: Int) {
/// 分割直到每片區(qū)域只有一個(gè)或2個(gè)元素排序退出
guard right - left > 1 else {
if right > left, self[left] > self[right] {
swapAt(left, right)
}
return
}
/// 將self分成2部分分別排序
let mid = (right + left) / 2
msort(left: left, right: mid)
msort(left: mid+1, right: right)
/// 將self中排好序的2部分合并排序到temp
var l = left
var r = mid+1
var i = left
while l <= mid, r <= right {
if self[l] < self[r] {
temp[i] = self[l]
l += 1
} else {
temp[i] = self[r]
r += 1
}
i += 1
}
/// 剩下的部分
while l <= mid {
temp[i] = self[l]
l += 1
i += 1
}
while r <= right {
temp[i] = self[r]
r += 1
i += 1
}
/// 排好序的temp賦值到self
for i in left...right {
self[i] = temp[i]
}
}
msort(left: 0, right: count - 1)
}
}
