import Foundation

func sort(_ arr1: [Int], _ arr2: [Int]) -> [Int] {
    var c = Array<Int>()
    var arr1 = arr1
    var arr2 = arr2
    let c1 = arr1.count
    let c2 = arr2.count
    if c1 > c2 {
        for _ in 0..<c2 {
            if arr1[0] < arr2[0] {
               c.append(arr1[0])
               arr1.removeFirst()
            } else {
                c.append(arr2[0])
                arr2.removeFirst()
            }
        }
        for leftItem in arr1 {
            c.append(leftItem)
        }
    } else{
        for _ in 0..<c1 {
            if arr1[0] < arr2[0] {
               c.append(arr1[0])
               arr1.removeFirst()
            } else {
                c.append(arr2[0])
                arr2.removeFirst()
            }
        }
        for leftItem in arr2 {
            c.append(leftItem)
        }
    }

    return c
}

func mergeSort(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else {
        return arr
    }
    let middleIndex = arr.count / 2
    let leftArray = mergeSort(Array(arr[0..<middleIndex]))
    let rightArray = mergeSort(Array(arr[middleIndex..<arr.count]))

    return sort(leftArray, rightArray)
}

var testCase1 = [1, 2, 3, 4, 5, 6, 7]
var testCase2 = [5, 6, 4, 3, 1, 0, 2]

print(mergeSort(testCase1))
print(mergeSort(testCase2))