Merge sort

func merge(arr: inout [Int], front: Int, end: Int, mid: Int) {
    var arr1 = [Int]()
    var arr2 = [Int]()
    for i in front ... mid {
        arr1.append(arr[i])
    }
    for i in (mid + 1) ... end {
        arr2.append(arr[i])
    }

    var i = 0
    var j = 0
    var k = front
    while i < arr1.count && j < arr2.count {
        if arr1[i] < arr2[j] {
            arr[k] = arr1[i]
            i += 1
            k += 1
        } else {
            arr[k] = arr2[j]
            j += 1
            k += 1
        }
    }
    
    while i < arr1.count {
        arr[k] = arr1[i]
        i += 1
        k += 1
    }
    
    while j < arr2.count {
        arr[k] = arr2[j]
        j += 1
        k += 1
    }
}

func mergeSort(arr: inout [Int], front: Int, end: Int) {
    if front < end {
        let mid = (front + end) / 2
        mergeSort(arr: &arr, front: front, end: mid)
        mergeSort(arr: &arr, front: mid + 1, end: end)
        merge(arr: &arr, front: front, end: end, mid: mid)
    }
}

var arr = [6, 5, 4, 3, 2, 1]
mergeSort(arr: &arr, front: 0, end: arr.count - 1)
print(arr)

Time complexity:

Best case: O(nlogn)

Average case: O(nlogn)

Worst case: O(nlogn)

Ref: https://www.geeksforgeeks.org/merge-sort/

Ref: http://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html