func mergeSort(_ array: [Int]) -> [Int] {
    return mergeSortPrivate(array)
}

private func mergeSortPrivate(_ array: [Int]) -> [Int] {
    if array.count <= 1 {return array}
    
    let tmpArr = array
    let count = array.count
    let middle = (count - 1) / 2

    let leftArr = mergeSortPrivate(Array(tmpArr[0...middle]))
    let rightArr = mergeSortPrivate(Array(tmpArr[middle+1...count-1]))
    return merge(leftArr, rightArr)
}

private func merge(_ arr1: [Int], _ arr2: [Int]) -> [Int] {
    var tmpArr = [Int]()
    var j = 0;
    var k = 0;
    while j < arr1.count && k < arr2.count {
        if arr1[j] <= arr2[k] {
            tmpArr.append(arr1[j])
            j += 1
        } else {
            tmpArr.append(arr2[k])
            k += 1
        }
    }
    
    if j == arr1.count {
        tmpArr += arr2[k..<arr2.count]
    } else {
        tmpArr += arr1[j..<arr1.count]
    }
    
    return tmpArr
}

print(mergeSort([0,5,3,2,8,9,1,5,2,4,6,8]))

[0, 1, 2, 2, 3, 4, 5, 5, 6, 8, 8, 9]