歸并排序的概念

/**
 * 歸并排序（Merge Sort）： 馮諾依曼 1945年提出
 * 1、不斷的將當(dāng)前序列平均分割成2個(gè)子序列，直到不能分割為止  //divide
 * 2、不斷的將2個(gè)子序列合并成一個(gè)有序序列，直到最終剩下1個(gè)有序序列  //merge
 */

歸并排序圖解.gif

歸并排序.png

/// Swift 代碼實(shí)現(xiàn)如下：
class MergeSort: NSObject {
    
    func mergeSort(_ array: [Int]) -> [Int] {
        guard array.count > 1 else {
            return array
        } // 1
        
        let middleIndex = array.count / 2              // 2
        
        let leftArray = mergeSort(Array(array[0..<middleIndex]))             // 3
        
        let rightArray = mergeSort(Array(array[middleIndex..<array.count]))  // 4
        
        return merge(leftPile: leftArray, rightPile: rightArray)             // 5
    }
    
    
    func merge(leftPile: [Int], rightPile: [Int]) -> [Int] {
        // 1
        var leftIndex = 0
        var rightIndex = 0
        
        // 2
        var orderedPile = [Int]()
        
        // 3
        while leftIndex < leftPile.count && rightIndex < rightPile.count {
            if leftPile[leftIndex] < rightPile[rightIndex] {
                orderedPile.append(leftPile[leftIndex])
                leftIndex += 1
            } else if leftPile[leftIndex] > rightPile[rightIndex] {
                orderedPile.append(rightPile[rightIndex])
                rightIndex += 1
            } else {
                orderedPile.append(leftPile[leftIndex])
                leftIndex += 1
                orderedPile.append(rightPile[rightIndex])
                rightIndex += 1
            }
        }
        
        // 4
        while leftIndex < leftPile.count {
            orderedPile.append(leftPile[leftIndex])
            leftIndex += 1
        }
        
        while rightIndex < rightPile.count {
            orderedPile.append(rightPile[rightIndex])
            rightIndex += 1
        }
        
        return orderedPile
    }

}