归并排序

参考链接

• 选择排序：简单选择排序（Simple Selection Sort）

• 白话经典算法系列之四 直接选择排序及交换二个数据的正确实现

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

基本思想

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

初始关键字 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个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。

综上可知，归并排序其实要做两件事：

（1）“分解”——将序列每次折半划分。

（2）“合并”——将划分后的序列段两两合并后排序。

算法的实现

extension Array where Element: Comparable {
    mutating func mergeSort() {
        var temp = self
        func msort(left: Int, right: Int) {
            /// 分割直到每片区域只有一个或2个元素排序退出
            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)
    }
}