Insertion Sort

Concept

Insertion Sort is exactly how humans intuitively sort a hand of playing cards.
You hold a sorted hand in your left hand. The dealer hands you a brand new card. You scan your sorted hand from right to left, find the exact spot where the new card mathematically belongs, and insert it.

While it is an $O(N^2)$ algorithm like Bubble and Selection Sort, it is vastly superior in practice. It is incredibly fast on small datasets and datasets that are almost perfectly sorted.

The Mechanism

Array: [5, 3, 8, 4, 2]

1. Index 0 (5): We pretend the first card is our fully sorted hand. Sorted Hand: [5]. Unsorted: [3, 8, 4, 2].
2. Index 1 (3): We pick up the 3. We look at our sorted hand. 5 is larger than 3, so we physically shift 5 to the right to make room. We insert 3 at the front. Sorted Hand: [3, 5].
3. Index 2 (8): We pick up the 8. We look at our sorted hand. 5 is smaller than 8. We don’t need to shift anything! We just slap the 8 at the end. Sorted Hand: [3, 5, 8].
4. Index 3 (4): Pick up the 4. Shift 8 right. Shift 5 right. 3 is smaller, so stop! Insert the 4 between 3 and 5. Sorted Hand: [3, 4, 5, 8].

Implementation

// Time Complexity: O(N^2) Worst, O(N) Best (Already sorted!)
// Space Complexity: O(1) In-Place

function insertionSort(nums: number[]): number[] {
    const n = nums.length;

    // Start at index 1, because we assume index 0 is our initial "Sorted Hand"
    for (let i = 1; i < n; i++) {
        // The card the dealer just gave us
        let currentCard = nums[i]; 
        
        // Point to the last card in our Sorted Hand
        let j = i - 1; 

        // Scan our sorted hand backwards (right to left).
        // If a card is LARGER than our new card, we shift it one spot to the right
        // to make physical space for our new card!
        while (j >= 0 && nums[j] > currentCard) {
            nums[j + 1] = nums[j]; // Shift the large card right
            j--; // Move to the next card to the left
        }

        // We found a smaller card, or we hit the beginning of the array.
        // The empty slot is exactly at j + 1. Insert the new card!
        nums[j + 1] = currentCard;
    }

    return nums;
}

The V8 Engine Secret

In JavaScript, V8 (Chrome/Node.js) used to implement Array.prototype.sort() using a hybrid algorithm.
If the array had more than 10 elements, it used Quick Sort.
If the array had 10 elements or fewer, it explicitly abandoned Quick Sort and used Insertion Sort!
(Modern V8 uses Timsort, which also heavily uses Insertion Sort for small chunks).

Why? Because $O(N \log N)$ algorithms like Quick Sort and Merge Sort carry massive recursive overhead. For incredibly small datasets ($N \le 10$), the raw physical execution speed of a simple $O(N^2)$ Insertion Sort while loop is actually faster than setting up the recursive Call Stack.

Interview Questions

Q: A stream of data is coming in, and the array is updated live. Which sorting algorithm is best?
A: Insertion Sort. It is an Online Algorithm. Because Insertion Sort inherently assumes the left side of the array is perfectly sorted, and simply inserts new elements one by one, it naturally handles streaming data in real-time perfectly. Selection Sort and Merge Sort require the entire dataset to exist upfront before they can even begin.

Q: Is Insertion Sort Stable?
A: Yes. while (nums[j] > currentCard). If we pull a 5B card, and compare it to a 5A card in our hand, 5A > 5B is False. It does not shift the 5A card. It legally inserts the 5B exactly after the 5A, perfectly maintaining stability.