Insertion Sort

Insertion Sort works the way we sort cards in our hand. It takes one element at a time and places it in its correct position within the already-sorted part of the array.

Algorithm

1. Start from the second element.
2. Compare it with the elements before it.
3. Shift larger elements to the right.
4. Insert the element at its correct position.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Example

data = [12, 11, 13, 5, 6]
print(insertion_sort(data))  # [5, 6, 11, 12, 13]

Visualization

[12, 11, 13, 5, 6]

i=1: key=11 -> shift 12 -> [11, 12, 13, 5, 6]
i=2: key=13 -> no shift -> [11, 12, 13, 5, 6]
i=3: key=5  -> shift 13, 12, 11 -> [5, 11, 12, 13, 6]
i=4: key=6  -> shift 13, 12, 11 -> [5, 6, 11, 12, 13]

Binary Insertion Sort

Uses binary search to find the insertion position, reducing the number of comparisons.

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        low, high = 0, i
        while low < high:
            mid = (low + high) // 2
            if arr[mid] > key:
                high = mid
            else:
                low = mid + 1

        # Shift elements
        for j in range(i, low, -1):
            arr[j] = arr[j - 1]
        arr[low] = key
    return arr

Time Complexity

Space Complexity

O(1) - in-place.

Characteristics

• Stable: Yes.
• In-place: Yes.
• Adaptive: Very efficient for nearly sorted data.
• Online: Can sort data as it arrives over time.

When to Use It

• Small datasets (n < 50).
• Nearly sorted data.
• As a subroutine in TimSort (Python, Java).
• When you need an in-place stable sort.

# Insertion sort is efficient for nearly sorted data
nearly_sorted = [1, 2, 4, 3, 5, 6, 8, 7, 9, 10]
# Only a few swaps needed -> approaches O(n)

Insertion Sort is simple and efficient for small data. Selection Sort is also simple but rarely used.