Swift 归并排序
基本原理:
对于两个有序子数组，合并成一个有序数组，是一个较为简单的事情。可以对两个子数组，从头开始遍历，并进行比较，如果哪个子数组的元素更需要排到前面，那么就把这个元素排到一个合并后的数组的前面。并移动该子数组的指针，指向下一个元素，合并后的数组也指向下一个元素，再进行下一轮比较。如果哪个数组已经指针移动到最后，那么另外的数组的剩余元素直接添加到合并后数组的当前位置后面。
如何把一个数组拆成两个有序数组，就需要使用递归。通过递归把数组拆成两个有序数组，如果还不是继续递归拆分。然后执行上面的合并逻辑。因为最终可以拆分成1个元素或者0个元素，所以，递归后，总是可以变成有序数组。说可以可以进行合并。
上代码
func mergeSort(arr: inout [Int], mergeTempArr: inout [Int], left: Int, right: Int) {
if left >= right {
return
}
let mid = left + (right - left) >> 1
mergeSort(arr: &arr, mergeTempArr: &mergeTempArr, left: left, right: mid)
mergeSort(arr: &arr, mergeTempArr: &mergeTempArr, left: mid + 1, right: right)
var i = left
var j = mid + 1
var k = left
while i <= mid, j <= right {
if arr[i] < arr[j] {
mergeTempArr[k] = arr[i]
i += 1
} else {
mergeTempArr[k] = arr[j]
j += 1
}
k += 1
}
while i <= mid {
mergeTempArr[k] = arr[i]
i += 1
k += 1
}
while j <= right {
mergeTempArr[k] = arr[j]
j += 1
k += 1
}
for index in left...right {
arr[index] = mergeTempArr[index]
}
}
var tempArr = arr
mergeSort(arr: &arr, mergeTempArr: &tempArr, left: 0, right: arr.count - 1)
print(arr)
