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

function doSort(items: number[], 
                fst: number, lst: number) {
    if (fst >= lst)
        return
    let i = fst
    let j = lst
    let x = items[Math.floor((fst + lst) / 2)]

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

function sort(arr: number[]): number[] {
    let items = arr.slice()
    doSort(items, 0, items.length - 1)
    return items
}

let items = [4, 1, 5, 3, 2]
let sortItems = sort(items)
// sortItems is [1, 2, 3, 4, 5]
console.log("sortItems is", 
    sortItems)

// *** simplified speed test ***
let i = 0
items = Array
    .apply(null, Array(200))
    .map(() => ++i)
let tmp = items[5]
items[5] = items[6]
items[6] = tmp
let count = 10000
let start = new Date()

for (i = 0; i < count; i++)
    sort(items)

let now = new Date()
let milliseconds = now.getTime() - start.getTime()

console.log("milliseconds is", milliseconds)
// about 3 milliseconds