Insertion Sort: The Art of Penetrating Sorted States

Chris is working on sorting 'log data' received from a server in chronological order.

However, this data is peculiar. 99% of it is already sorted by time, and only a few logs that arrived late are mixed up out of order.

"It's already nearly sorted, so wouldn't using Bubble Sort or Selection Sort be a waste of time since they compare everything from start to finish?"

"Wouldn't it be finished if I just picked out the ones stuck in the middle and inserted them into their proper places?"

Exactly. This is the method we use to organize cards when playing a card game, and the algorithm that shines when data is nearly sorted. It is Insertion Sort.

1. The Wisdom of Card Games

The logic of Insertion Sort is very intuitive.

Imagine arranging cards held in your hand from left to right.

The core idea is "Assume the front part is already sorted, and insert the new card into the appropriate position."

2. Implementing in JavaScript

The key to implementation is comparing "Backwards." You push (Shift) elements larger than the target one step back, and when a spot opens up, you settle in.

function insertionSort(arr) {
  // 1. Start from the second element (i=1). (Assume the first is already sorted)
  for (let i = 1; i < arr.length; i++) {
    let currentVal = arr[i]; // The card to organize now
    let j;

    // 2. Compare with cards in front (j) and go backwards.
    // Condition: j is >= 0 AND the card in front is larger than me (currentVal)?
    for (j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      arr[j + 1] = arr[j]; // Shift the front card one step back. (Copy)
    }

    // 3. Sit right behind where the loop ended (where we met a smaller card).
    arr[j + 1] = currentVal;
    
    console.log(`Step {i}:`, arr); // Let's check the process
  }
  return arr;
}

insertionSort([2, 1, 9, 76, 4]);

3. Why is 'Insertion Sort' Special?

Looking at the code, it looks like a nested loop, similar to Bubble or Selection sort. However, there is a decisive difference.

Smart Break

Bubble and Selection sorts compare unconditionally to the end regardless of the state.

However, Insertion Sort stops the inner loop (j) immediately when it meets a value smaller than itself. Because the part in front of me is already sorted, there is no need to look further.

The Best Case: O(N)

What if the data is already sorted?

Insertion Sort checks each element only once, thinks "Oh? The one in front is smaller than me? Then I'll just stay here," and moves on immediately.

The time complexity in this case is O(N). It is incomparably faster than Bubble or Selection sort (O(N^2)).

Online Algorithm

It is also useful in situations where data is not given all at once but comes in one by one in real-time (like live streaming chats). You just need to find the right place and insert it whenever data arrives.

4. Are There No Downsides?

Of course, it's not a silver bullet.

It is the worst if the data is sorted in Reverse order.

To sort [5, 4, 3, 2, 1], every element must be moved to the very front every time, taking O(N^2) time. It is also O(N^2) on average when data is randomly shuffled.

Key Takeaways

The three sorting algorithms we've learned so far (Bubble, Selection, Insertion) are easy to implement, but too slow to use if data exceeds 100,000 items.

From now on, we enter the world of O(N log N), which shows speed on a different dimension.

The magic of Divide and Conquer, which says "It gets faster if you split the data."

Let's meet the first runner, Merge Sort.

🔗 References