參考鏈接

• 選擇排序：簡(jiǎn)單選擇排序（Simple Selection Sort）

• 白話(huà)經(jīng)典算法系列之四 直接選擇排序及交換二個(gè)數(shù)據(jù)的正確實(shí)現(xiàn)

歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法（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)
    }
}