9.6 Insertion Sort

Insertion Sort is a simple and intuitive sorting algorithm that builds the final sorted array one item at a time. It is often compared to how one might sort a hand of playing cards. Insertion Sort is particularly efficient for small datasets or datasets that are already partially sorted.

What is Insertion Sort?

The algorithm works by taking elements from the unsorted portion of the list and inserting them into their correct position within the already sorted portion. At each step, it ensures that the subarray from the beginning up to the current element is sorted.

Algorithm Steps

1. Start with the second element (index 1) of the array. This element is considered the key to be inserted into its correct position.
2. Compare the key with the elements to its left in the already sorted portion of the array.
3. Shift elements: If an element to the left is greater than the key, shift that element one position to the right to make space for the key. Continue this process until an element smaller than or equal to the key is found, or the beginning of the array is reached.
4. Insert the key: Place the key into the vacated position.
5. Repeat this process for every element in the array, moving from left to right.

Python Implementation

def insertion_sort(arr):
    """
    Sorts an array using the Insertion Sort algorithm.

    Args:
        arr: A list of comparable elements.
    """
    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
        key = arr[i]  # The element to be inserted into its correct position
        j = i - 1     # The index of the last element in the sorted subarray

        # 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]
            j -= 1
        
        # Insert the key at its correct position
        arr[j + 1] = key

Example Usage

data = [9, 5, 1, 4, 3]
insertion_sort(data)
print("Sorted array:", data)

Output:

Sorted array: [1, 3, 4, 5, 9]

Step-by-Step Walkthrough

Let's trace the execution with [9, 5, 1, 4, 3]:

1. Initial Array: [9, 5, 1, 4, 3]
2. i = 1 (key = 5):
   • Compare 5 with 9. 9 > 5, so shift 9 to the right: [_, 9, 1, 4, 3]
   • j becomes -1.
   • Insert 5 at j+1 (index 0): [5, 9, 1, 4, 3]
3. i = 2 (key = 1):
   • Compare 1 with 9. 9 > 1, shift 9: [5, _, 9, 4, 3]
   • Compare 1 with 5. 5 > 1, shift 5: [_, 5, 9, 4, 3]
   • j becomes -1.
   • Insert 1 at j+1 (index 0): [1, 5, 9, 4, 3]
4. i = 3 (key = 4):
   • Compare 4 with 9. 9 > 4, shift 9: [1, 5, _, 9, 3]
   • Compare 4 with 5. 5 > 4, shift 5: [1, _, 5, 9, 3]
   • Compare 4 with 1. 1 < 4, stop shifting.
   • Insert 4 at j+1 (index 2): [1, 4, 5, 9, 3]
5. i = 4 (key = 3):
   • Compare 3 with 9. 9 > 3, shift 9: [1, 4, 5, _, 9]
   • Compare 3 with 5. 5 > 3, shift 5: [1, 4, _, 5, 9]
   • Compare 3 with 4. 4 > 3, shift 4: [1, _, 4, 5, 9]
   • Compare 3 with 1. 1 < 3, stop shifting.
   • Insert 3 at j+1 (index 1): [1, 3, 4, 5, 9]

The array is now sorted.

Time and Space Complexity

• Time Complexity:

  • Best Case: O(n) - Occurs when the input array is already sorted. In this case, each element is compared only once with the element immediately preceding it.
  • Average Case: O(n²) - Occurs when the input array is in a random order.
  • Worst Case: O(n²) - Occurs when the input array is sorted in reverse order.

• Space Complexity: O(1) - Insertion Sort is an in-place sorting algorithm, meaning it does not require any additional auxiliary space proportional to the input size.

Key Characteristics

• Simplicity: Easy to understand and implement.
• Efficiency for Small Datasets: Performs very well for small arrays.
• Efficiency for Nearly Sorted Data: Its performance degrades gracefully as data becomes less sorted.
• Stable: Maintains the relative order of equal elements.
• In-place: Requires constant extra space.
• Adaptive: Can detect if the list is already sorted (or nearly sorted) and runs faster.

When to Use Insertion Sort

Insertion Sort is a good choice in the following scenarios:

• Small datasets: For arrays with fewer than 50 elements, Insertion Sort can be faster than more complex algorithms due to its low overhead.
• Nearly sorted arrays: When the data is already mostly sorted, Insertion Sort performs exceptionally well, approaching O(n) time complexity.
• Online sorting: It can sort data as it arrives, without needing the entire dataset beforehand.
• When stability is required: If the order of equal elements needs to be preserved.
• Educational purposes: It's often used as a starting point for teaching sorting algorithms due to its simplicity.

Comparison with Other Algorithms

Interview Questions

• What is Insertion Sort and how does it work?
• What is the time complexity of Insertion Sort in best, average, and worst cases?
• Is Insertion Sort a stable algorithm? Explain.
• Compare Insertion Sort with Bubble Sort and Merge Sort.
• Why is Insertion Sort efficient for nearly sorted arrays?
• How does Insertion Sort achieve in-place sorting?
• When is Insertion Sort preferred over other algorithms?
• Write the Python code for Insertion Sort and explain each step.
• How many swaps are required in Insertion Sort for a sorted array?
• Can Insertion Sort be used in real-time systems? Why or why not?