Insertion Sort

Insertion Sort Algorithm

After learning Bubble Sort and Selection Sort, we move to our third foundational sorting algorithm: Insertion Sort.

This algorithm is very intuitive. It is the natural way humans tend to sort physical items!

1. How Does Insertion Sort Work?

Insertion Sort divides the array into a sorted part and an unsorted part, just like Selection Sort.

However, instead of looking for the smallest item, Insertion Sort simply picks up the very first unsorted item. It then scans backward through the sorted part and inserts the item into its exact correct position.

Real-Life Analogy

Imagine you are holding a hand of playing cards.

1. You hold the first card in your left hand. It is already "sorted" because it's the only card.
2. Your right hand picks up the next card from the deck.
3. You compare it to the cards in your left hand.
4. You slide it into the correct position.
5. You repeat this until there are no cards left in the deck.

Insertion Sort: Pick the next element and shift existing elements right to make room for it.

2. A Step-by-Step Example

Let's sort an array: [5, 3, 8, 4, 2]

Pass 1:

• Sorted part: [5]. Unsorted: [3, 8, 4, 2].
• Pick up 3. Compare it to 5.
• 3 is smaller, so shift 5 to the right and insert 3.
• Array is now: [3, 5, 8, 4, 2].

Pass 2:

• Sorted part: [3, 5]. Unsorted: [8, 4, 2].
• Pick up 8. Compare it to 5.
• 8 is larger, so it is already in the correct spot! Leave it alone.
• Array is now: [3, 5, 8, 4, 2].

Pass 3:

• Sorted part: [3, 5, 8]. Unsorted: [4, 2].
• Pick up 4.
• 4 is smaller than 8. Shift 8 right.
• 4 is smaller than 5. Shift 5 right.
• 4 is larger than 3. Insert 4 here!
• Array is now: [3, 4, 5, 8, 2].

Pass 4:

• Pick up 2. Shift 8, 5, 4, 3 to the right. Insert 2 at the very beginning.
• Array is finally sorted: [2, 3, 4, 5, 8].

3. Insertion Sort Code Example

Let's write the Insertion Sort algorithm in Python. Pay attention to the while loop that handles shifting the larger elements to the right!

def insertion_sort(arr):
    # Start from 1, because index 0 is already "sorted"
    for i in range(1, len(arr)):
        key = arr[i] # The element we want to insert
        j = i - 1
        # Move elements that are greater than key
        # to one position ahead of their current position
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        # Insert the key in its correct position
        arr[j + 1] = key
    return arr

numbers = [5, 3, 8, 4, 2]
print("Original:", numbers)
print("Sorted:", insertion_sort(numbers))

4. Time Complexity

• Worst Case Time Complexity: O(n²). If the array is sorted in reverse, you have to shift every single element to the right for every new item you insert.
• Best Case Time Complexity: O(n). This is where Insertion Sort shines! If the array is already sorted, the inner while loop never runs. It just checks each item once and moves on.
• Space Complexity: O(1). Memory usage is minimal since it sorts in-place.

Because of its O(n) best-case scenario, many modern programming languages actually use a hybrid of Insertion Sort and other algorithms (like Merge Sort) to handle small datasets under the hood!