归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)

var array = [10, 5, 8, 2, 22, 12, 8]
        mergeSort(&array)
        
        /**归并排序*/
        func mergeSort(_ nums:inout [Int]) {

            sort(&nums, left: 0, right: nums.count-1)
        }
        func sort(_ nums:inout [Int], left: Int, right: Int){
            guard left < right else {
                return
            }
            let mid = (left+right) >> 1
            sort(&nums, left: left, right: mid)
            sort(&nums, left: mid+1, right: right)
            merg(&nums, left: left, mid: mid, right: right)
        }
        func merg(_ array:inout [Int], left: Int, mid: Int, right:Int){
            var i = left  //左指针
            var j = mid+1  //右指针
            var t = 0       //临时数组指针
            var temp = [Int]()
            while i<=mid, j<=right {
                if array[i] < array[j] {
                    temp.append(array[i])
                    i += 1
                }else{
                    temp.append(array[j])
                    j += 1
                }
            }
            while i <= mid {  //左边如还有剩余，加入temp数组
                temp.append(array[i])
                i += 1
            }
            while j <= right {  //右边如还有剩余，加入temp数组
                temp.append(array[j])
                j += 1
            }
            t = 0
            i = left
            //将temp移动到原数组
            while i <= right {
                array[i] = temp[t]
                t += 1
                i += 1
            }
            print("当前排序\(temp)左=\(left),中=\(mid), 右=\(right)结果:\(array)")
        }