// Time Complexity from O(n log(n)) to O(n^2)
// Space Complexity O(log(n))

func doSort(_ items: inout [Int], _ fst: Int, _ lst: Int) {
    if fst >= lst {
        return
    }
    var i = fst
    var j = lst
    let x = items[(fst + lst)/2]

    while (i < j) {
        while items[i] < x { i+=1 }
        while items[j] > x { j-=1 }
        if (i <= j) {
            let tmp = items[i]
            items[i] = items[j]
            items[j] = tmp
            i+=1
            j-=1
        }
    }
    doSort(&items, fst, j)
    doSort(&items, i, lst)
}

func sort(_ arr: [Int]) -> [Int]
{
    var items = arr
    doSort(&items, 0, items.count - 1)
    return items
}


var items = [ 4, 1, 5, 3, 2 ]

var sortItems = sort(items)
// sortItems is {1, 2, 3, 4, 5}
print(sortItems)

// *** simplified speed test ***
items = [Int](repeating: 0, count: 200)
for i in 0 ..< items.count {
    items[i] = i
}
let tmp = items[5]
items[5] = items[6]
items[6] = tmp

let count = 100
let start = Date()

for _ in 0 ..< count {
    sortItems = sort(items)
}

let seconds = abs(start.timeIntervalSinceNow)

print(sortItems)
print(seconds)
// about 0.008698 seconds