//  ViewController.swift
//  MergeSort
//
//  Created by DworldAI on 2021/11/5.
//

import UIKit

class ViewController: UIViewController {

    var leftArr = [Int]()
    override func viewDidLoad() {
        super.viewDidLoad()

        var arr = [2,5,2,3,9,6,2,100,33,3,45,2,3,9,6,2,100,33,3,45,2,3,9,6,2,100,33,3,45,2,3,9,6,2,100,33,3,4]

        let startTime = CFAbsoluteTimeGetCurrent()
        self.sort(arr: &arr, start: 0, end: arr.count)
                
        let endTime = CFAbsoluteTimeGetCurrent()
        print("代碼執(zhí)行時(shí)長(zhǎng)：%f 毫秒", (endTime - startTime)*1000)
        
    }
    
    func sort(arr:inout [Int],start:Int,end:Int){
        if end - start < 2{
            return
        }
        let mid = (end + start)/2
        sort(arr: &arr, start: start, end: mid)
        sort(arr: &arr, start: mid, end: end)
        self.mergee(arr: &arr, begin: start, mid: mid, end: end)
    }
    
    func mergee( arr:inout [Int],begin:Int,mid:Int,end:Int) {
        
        var li = 0
        let le = mid - begin
        var ri = mid
        let re = end
        var ai = begin

        leftArr = [Int]()
        for dex in 0 ..< le {
            leftArr.append(arr[begin + dex])
        }
        while li < le {
            if ri < re,leftArr[li] > arr[ri] {
                arr[ai] = arr[ri]
                ai = ai + 1
                ri = ri + 1
            }else{
                arr[ai] = leftArr[li]
                 ai = ai + 1
                 li = li + 1
            }
        }

    }
    

    //排序入口
    func mergeSort(arr:inout [Int]) {
        if arr.count <= 1 {
            return
        }
        process(arr: &arr, left: 0, right: arr.count - 1)
    }
    //該方法主要用作二分
    func process(arr:inout [Int],left:Int,right:Int) {
        if left == right {
            return
        }
        let middle = left + (right - left) >> 1
        process(arr: &arr, left: left, right: middle)
        process(arr: &arr, left: middle + 1, right: right)
        merge(arr: &arr, left: left, middle: middle, right: right)
    }
    //將二分后的數(shù)組進(jìn)行合并
    func merge(arr:inout [Int],left:Int,middle:Int,right:Int){
        var help:[Int] = [Int]()

        var leftLocation:Int = left
        var rightLocation:Int = middle + 1

        while (leftLocation <= middle && rightLocation <= right) {
            if arr[leftLocation] <= arr[rightLocation] {
                help.append(arr[leftLocation])
                leftLocation += 1
            }else{
                help.append(arr[rightLocation])
                rightLocation += 1
            }
        }

        while leftLocation <= middle {
            help.append(arr[leftLocation])
            leftLocation += 1
        }
        while rightLocation <= right {
            help.append(arr[rightLocation])
            rightLocation += 1
        }
        var index = left
        for item in help {
            arr[index] = item
            index += 1
        }

    }

}