归并排序核心就是合并两个已经排好序的数组

// 合并两个已经排好序的数组
func mergeTwoArray(array1: [Int],array2: [Int])->[Int]{
    
    var resultArray = [Int]()
    var firstIndex: Int = 0
    var secondIndex: Int = 0
    
    while firstIndex < array1.count && secondIndex < array2.count {
        if array1[firstIndex] < array2[secondIndex]{
            resultArray.append(array1[firstIndex])
            firstIndex += 1
        }else{
            resultArray.append(array2[secondIndex])
            secondIndex += 1
        }
    }

    while firstIndex < array1.count {
        resultArray.append(array1[firstIndex])
        firstIndex += 1
    }
    while secondIndex < array2.count {
        resultArray.append(array2[secondIndex])
        secondIndex += 1
    }
    return resultArray
}

归并排序

func mergeSort(array: [Int])-> [Int]{
    // 二维数组
    var tempArray: Array<Array<Int>> = []
    for item in array {
        var subArray: Array<Int> = [Int]()
        subArray.append(item)
        tempArray.append(subArray)
    }
    
    while tempArray.count != 1 {
        var i = 0
        while i < tempArray.count - 1 {
            tempArray[i] = mergeTwoArray(array1: tempArray[i], array2:  tempArray[i+1])
            tempArray.remove(at: i+1)
            i = i+1
        }
    }
    return tempArray.first!
}

demo

递归算法

// [1,4,3,5]
func mergeSort(_ array: [Int]) -> [Int] {
    print("times==============times")
    // 递归基线条件 array.count <= 1
    guard array.count > 1 else { return array }    // 1
    let middleIndex = array.count / 2              // 2
    // 递归条件
    let leftArray = mergeSort(Array(array[0..<middleIndex]))             // 3
    print("leftArray----------\(leftArray)")
    print("middleIndex=\(middleIndex)  array=\(array)")
    // 递归条件
    let rightArray = mergeSort(Array(array[middleIndex..<array.count]))  // 4
    print("rightArray----------\(rightArray)")
    return mergeTwoArray(array1: leftArray, array2: rightArray)        // 5
}

递归的一个循环是指一整个函数

比如步骤3,调用自己,截止到递归结束条件,如下,打印3次times==============times

步骤4,调用自己,截止到递归结束条件,如下,打印1次times==============times

步骤5,返回值并不是直接结束了整个函数,而是leftArray----------[1, 4]

middleIndex=2 array=[1, 4, 3, 5]有点绕

times==============times
times==============times
times==============times
leftArray----------[1]
middleIndex=1  array=[1, 4]
times==============times
rightArray----------[4]
leftArray----------[1, 4]
middleIndex=2  array=[1, 4, 3, 5]
times==============times
times==============times
leftArray----------[3]
middleIndex=1  array=[3, 5]
times==============times
rightArray----------[5]
rightArray----------[3, 5]
[1, 3, 4, 5]