归并排序.md

归并排序是将一组序列分解按照等分依次分解，最后成为只有一个元素的小数组，最后将数组合并之后排序成为整体的数组的一种排序方法。

归并排序图解

分解数组

将数组【8 3 6 12 1】按照平均数划分

将数组【8 3】和数组【6 12 1】进行平分

将数组【12 1】进行评分

合并数组

将数组【8】和数组【3】进行合并

取出第一个元素8和第一个元素3对比，将3放入到新数组

数组【3】完毕，将第一个数组全部放在新数组中

将数组【12】和数组【1】进行合并

取出第一个元素12和1对比，将1放到新数组中

数组【1】完成，将第一个数组全部放在新数组中

将数组【6】和数组【1 12】合并

取出第一个元素6和第一个元素1对比，将1放入新数组

取出第一个元素6和第二个元素12对比，将6放入到新数组中

数组【6】完毕，将第二个数组剩余全部放在新数组中

将数组【3 8】和数组 【1 6 12】进行合并

取出第一个元素3和第一个元素1对比，将1加入到新数组中

将第一个元素3和第二个元素6对比，将3加入到新数组中

将第二个元素8和第二个元素6对比，将6添加到新数组中

将第二个元素8和第三个元素12对比，将8加入到新数组

数组【3 8】完毕将第二个数组全部加入到新数组中

到底归并排序完成

示例代码

class Solution {
    func mergeSort(_ numbers:[Int]) -> [Int] {
        guard numbers.count > 1 else {
            return numbers
        }
        guard let cuts = cutList(numbers) else {
            return numbers
        }
        return mergeList(cuts.0, cuts.1)
    }
    func cutList(_ numbers:[Int]) -> ([Int],[Int])? {
        guard numbers.count > 1 else {
            return nil
        }
        let cut:Int = numbers.count / 2
        let leftNumbers = mergeSort(Array(numbers[0 ..< cut]))
        let rightNumber = mergeSort(Array(numbers[cut...]))
        return (leftNumbers, rightNumber)
    }
    
    func mergeList(_ left:[Int], _ right:[Int]) -> [Int] {
        guard left.count > 0 else {
            return left
        }
        guard right.count > 0 else {
            return left
        }
        var list:[Int] = []
        var i = 0
        var j = 0
        while true {
            guard left.count > i || right.count > j else {
                break
            }
            if left.count <= i {
                list.append(right[j])
                j += 1
            } else if right.count <= j {
                list.append(left[i])
                i += 1
            } else {
                let n1 = left[i]
                let n2 = right[j]
                if n1 < n2 {
                    list.append(n1)
                    i += 1
                } else {
                    list.append(n2)
                    j += 1
                }
            }
        }
        return list
    }
}