Insertion Sort

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration.

It is similar to the way we sort playing cards in our hands. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left. At all times, the cards held in the left hand are sorted, and these cards were originally the top cards of the pile on the table.

Time Complexity

Worst-case: O(n2)
Average-case: O(n2)

Visualization

Canvas

Code

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let j = i - 1;
        let key = arr[i];
        
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;
    }
}

Copied to clipboard!