Bubble sort

// Time Complexity O(n^2)
// Space Complexity O(1)
// neighbours change places until a pass makes no swaps:
// the largest element "bubbles up" to the end on every pass

function sort(arr: number[]) {
    let items = arr.slice()
    for (let end = items.length; end > 1; end--) {
        let swapped = false
        for (let j = 1; j < end; j++) {
            if (items[j] < items[j - 1]) {
                let tmp = items[j]
                items[j] = items[j - 1]
                items[j - 1] = tmp
                swapped = true
            }
        }           
        if (!swapped) {
            break
        }
    }
    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)
    .reverse()
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 166 milliseconds