Insertion Sort

Insertion Sort is a simple, comparison-based sorting algorithm that builds the sorted array one item at a time by gradually inserting elements into their correct position. It is efficient for small datasets and partially sorted data, making it a commonly taught algorithm for introductory sorting.

Let’s go over the theoretical aspects, code example with type hints, common pitfalls, and interview tips.

Insertion Sort: The Basics

Insertion Sort works similarly to the way we sort playing cards in our hands:

1. Starting from the second element, compare it with each preceding element.
2. Insert it into the correct position among the already sorted elements to the left.
3. Repeat the process for all elements until the array is sorted.

Time Complexity:

• Worst and Average Case: O(n²), as each element may need to be compared with all previous elements.
• Best Case: O(n), if the array is already sorted.

Space Complexity: O(1), as it requires only a constant amount of additional memory.

Stability: Insertion Sort is a stable sorting algorithm, meaning it preserves the relative order of elements with equal values.

Insertion Sort Algorithm Steps

1. Outer Loop: Start from the second element, treating the first element as a sorted subarray.
2. Inner Loop: For each element, compare it with elements in the sorted portion (to its left) and shift larger elements one position to the right until the correct spot for the current element is found.
3. Insert Element: Place the current element in its correct position within the sorted subarray.

Code Example: Insertion Sort

from typing import List

def insertion_sort(arr: List[int]) -> None:
    """
    Perform insertion sort on the input array `arr`.
    - arr: List of integers to be sorted (in place)
    """
    for i in range(1, len(arr)):
        key = arr[i]  # Current element to be inserted into the sorted portion
        j = i - 1
        # Move elements of arr[0..i-1], 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]  # Shift the larger element one position to the right
            j -= 1
        
        # Insert the key at the correct position
        arr[j + 1] = key

# Example usage
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array:", arr)
# Output: Sorted array: [5, 6, 11, 12, 13]

Explanation of Code

1. Outer Loop: The loop variable i starts at the second element (index 1), since the first element is considered a sorted subarray.
2. Inner Loop: The inner while loop shifts elements of the sorted portion (arr[0..i-1]) that are greater than the current key to the right by one position. This creates the correct spot for key.
3. Insertion: After shifting larger elements, the key is inserted at its correct position within the sorted portion.

Example Execution: For an array [12, 11, 13, 5, 6]: 1. Pass 1: [11, 12, 13, 5, 6] 2. Pass 2: [11, 12, 13, 5, 6] 3. Pass 3: [5, 11, 12, 13, 6] 4. Pass 4: [5, 6, 11, 12, 13]