합병 정렬

func mergeSort(array: inout [Int], startIndex: Int, endIndex: Int){
    if(startIndex < endIndex){
        let midIndex = (startIndex + endIndex) / 2
        mergeSort(array: &array, startIndex: startIndex, endIndex: midIndex)
        mergeSort(array: &array, startIndex: midIndex + 1, endIndex: endIndex)
        merge(array: &array, startIndex: startIndex, midIndex: midIndex, endIndex: endIndex)
    }
}
func merge(array: inout [Int], startIndex: Int, midIndex: Int, endIndex: Int){
    var i: Int = startIndex
    var j: Int = midIndex + 1
    var k: Int = startIndex
    var tempArray: [Int] = Array(repeating: 0, count: array.count)
    while(i <= midIndex && j <= endIndex){
        if(array[i] <= array[j]){
            tempArray[k] = array[i]
            i += 1
        } else {
            tempArray[k] = array[j]
            j += 1
        }
        k += 1
    }
    while(i <= midIndex){
        tempArray[k] = array[i]
        k += 1
        i += 1
    }
    while(j <= endIndex){
        tempArray[j] = array[j]
        k += 1
        j += 1
    }
    for a in startIndex...endIndex{
        array[a] = tempArray[a]
    }
}

탐색할 인덱스를 점차 줄여나가는 것으로 문제를 분할한다.

합병정렬 시 여분의 배열을 만들고 그 곳에 함수의 결과를 넣어 원래 배열을 갱신한다.