import UIKit

func merge(leftPile: [Int], rightPile: [Int]) -> [Int]{
    print(leftPile,"...\(rightPile)")

    var leftIndex = 0, rightIndex = 0
    var mergedPile = [Int]()

    while leftIndex < leftPile.count && rightIndex < rightPile.count {
        if leftPile[leftIndex] < rightPile[rightIndex] {
            mergedPile.append(leftPile[leftIndex])
            leftIndex += 1
        } else if leftPile[leftIndex] > rightPile[rightIndex] {
            mergedPile.append(rightPile[rightIndex])
            rightIndex += 1
        } else {
            mergedPile.append(leftPile[leftIndex])
            leftIndex += 1
            mergedPile.append(rightPile[rightIndex])
            rightIndex += 1
        }
    }

    while leftIndex < leftPile.count {
        mergedPile.append(leftPile[leftIndex])
        leftIndex += 1
    }

    while rightIndex < rightPile.count {
        mergedPile.append(rightPile[rightIndex])
        rightIndex += 1
    }
    print(mergedPile)
    return mergedPile
}

/*
 let numbers = [2, 1, 5, 9, 4]
 let arr = mergeSort(array: numbers)

 [2, 1, 5, 9, 4]
 [2, 1]
 [2]
 [1]
 [2]...[1]
 [1, 2]
 [5, 9, 4]
 [5]
 [9, 4]
 [9]
 [4]
 [9]...[4]
 [4, 9]
 [5]...[4, 9]
 [4, 5, 9]
 [1, 2]...[4, 5, 9]
 */