import Foundation


func merge(_ a: [Int], _ b: [Int]) -> [Int] {
    
    var i = 0
    var j = 0
    
    var sorted = [Int]()
    
    while i < a.count && j < b.count {
        
        if a[i] < b[j] {
            sorted.append(a[i])
            i += 1
        } else {
            sorted.append(b[j])
            j += 1
        }
    }
    
    for n in i..<a.count {
        sorted.append(a[n])
    }
    for n in j..<b.count {
        sorted.append(b[n])
    }
    
    return sorted
}




func mergeSort(_ a: [Int]) -> [Int]{
    
    if a.count > 1 {
        let middle = a.count / 2
        
        let left = mergeSort(Array(a[0..<middle]))
        let right = mergeSort(Array(a[middle..<a.count]))
        
        return merge(left, right)
    }
    
    return a
}


mergeSort([3, 2, 5, 1, 4])