Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An implementation of insertion sort
// Average case O(n^2)
function insertionSort (arr) {
// Begin at position 1, because we need to compare the element at
// that position to the previous element
for (let i = 1; i < arr.length; i++) {
let j = i
// If the prior element is greater than the current element (arr[j]), swap
while (j > 0 && arr[j-1] > arr[j]) {
// Storing the tmp variable requires O(1) memory space
let tmp = arr[j]
arr[j] = arr[j-1]
arr[j-1] = tmp
j--
}
}
return arr
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment