insertionSort

Hard · Array Manipulations · 1 test cases

Implement the insertion sort algorithm to sort an array of numbers in ascending order.

Examples

insertionSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]) → [1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643]

Starter code

function insertionSort(arr) {

}

Complexity of the optimal solution

Time O(n²), space O(1). Insertion sort has a main loop that goes from the second element to the end. For each element, a nested while loop may shift elements to the right. In the worst case (a reverse-sorted array), this results in O(n²) comparisons and swaps. The sort is in-place, so space is constant.

Solve insertionSort in the browser