✨ Sorting Algorithm Series – Part 3: Insertion Sort

Deep Research on Insertion Sort

If you’ve ever sorted a hand of playing cards, you’ve already used the logic behind Insertion Sort. It builds a sorted array one element at a time, inserting each new element into the right position in the sorted portion.

🔹 What is Insertion Sort?

Insertion Sort works by dividing the array into two parts:

1. Sorted part – elements that are already in order

2. Unsorted part – the elements we still need to place

At each step, the algorithm picks the next element from the unsorted part and inserts it into its correct position in the sorted part.

Think of it like this: every time you pick up a new card, you slide it into the right spot in your hand.

🔹 When to Use Insertion Sort

✅ Good for:

• Small datasets

• Nearly sorted arrays (adaptive nature makes it very efficient here)

❌ Not good for:

• Large datasets (because of O(n²) complexity)

🔹 Where is Insertion Sort Used in Practice?

Although it’s not ideal for large datasets, Insertion Sort does appear in real-world scenarios:

• Databases & indexing operations – when small chunks of data need quick sorting.

• Hybrid algorithms like Timsort – used in Python’s built-in sort() and Java’s Arrays.sort() for small arrays before switching to more efficient algorithms.

• Educational contexts – to teach the fundamentals of sorting.

🔹 Time Complexity

• Best case: O(n) → when the array is already sorted

• Average case: O(n²)

• Worst case: O(n²)

🔹 Algorithm

void insertionSort(array) {
    int n = length of array
    repeat i from 1 to n-1 {
        key = array[i]
        int j = i - 1
        repeat until j >= 0 AND array[j] is greater than key {
            array[j + 1] = array[j]
            j = j - 1
        }
        array[j + 1] = key
    }
    return array
}

🔹Step by Step Example Visualization breakdown

Pass 1

Pass 2

Pass 3

Pass 4

🔹 Key Takeaways

• Insertion Sort is simple, intuitive, and works well on small or nearly sorted arrays.

• It’s adaptive: performs better when the array is almost sorted.

• It’s used in hybrid sorting algorithms (like Timsort) that power real-world languages.

✨ Next up in the series: Merge Sort – a powerful divide-and-conquer algorithm that drastically improves efficiency over Bubble, Selection, and Insertion Sort.

👉 Subscribe to follow the full Sorting Algorithm Series and get every post delivered to your inbox!