Insertion Sort

1. Introduction

1.1. How does Insertion Sort work?

Insertion Sort is a way to sort a list by gradually building up a sorted part. It is like sorting playing cards in your hands. You split the cards into two groups: the sorted cards and the unsorted cards. Then, pick a card from the unsorted group and put it in the right place in the sorted group.

Here is actually how the Insertion Sort works:

Begin with a list. Initially, the first number by itself is considered "sorted".
Then, for each new number that follows, the sorted portion is examined to determine the correct place for it.
The new number is compared with the numbers already in the sorted portion, and the numbers are shifted as necessary until the new number fits in perfectly.
This procedure continues until every number in the list is in its proper place.

1.2. Illustration of Insertion Sort

Insertion sort animation

Illustration of Insertion Sort

2. Code

        const insertionSort = (arr) => {
            let sortedArr = [...arr]; // A copy of the array

            for(let i = 1; i < sortedArr.length; i++) {
                let key = arr[i];
                let j = i - 1;

                /* Move elements of arr[0..i-1], that are greater than key, 
                to one position ahead of their current position */
                while (j >= 0 && sortedArr[j] > key) {
                    sortedArr[j + 1] = sortedArr[j];
                    j -= 1;
                }
                sortedArr[j + 1] = key;
            }
            return sortedArr;
        };

        const arr = [23, 1, 10, 5, 2];
        document.getElementById('originalArray').textContent = "Original Array: " + arr;

        const sortedArr = insertionSort(arr);
        document.getElementById('sortedArray').textContent = "Sorted Array: " + sortedArr;

Output:

Explanation

The initial array: 
        [23, 1, 10, 5, 2].
The first element (23) is considered sorted by itself.
        23 > 1? → [1, 23, 10, 5, 2]
        23 > 10? → [1, 10, 23, 5, 2]
        23 > 5? → [1, 10, 5, 23, 2], 10 > 5? → [1, 5, 10, 23, 2],
                                     5 > 1? → [1, 5, 10, 23, 2]
        23 > 2? → [1, 5, 10, 2, 23], 10 > 2? → [1, 5, 2, 10, 23],
                                     5 > 2? → [1, 2, 5, 10, 23],
                                     2 > 1? → [1, 2, 5, 10, 23]

4. Conclusion

Simplicity: Easy to implement & understand.

Efficiency on Small Data: Stable and works quickly on small or nearly sorted arrays, though its worst-case time complexity is O(n²).

Practically: Often used in hubrid sorts for its simplicity and low space complexity (O(1) extra space).

Insertion sort & Bubble sort: Insertion sort inserts each element into its correct position with fewer moves, while Bubble sort repeatedly swaps adjacent elements, making insertion sort typically more efficient on small or nearly sorted data.