Insertion Sort Algorithm: A Step-by-Step Guide

Insertion sort is a simple sorting algorithm that works by repeatedly inserting an element into its correct position in an already sorted array. It’s efficient for small datasets and can be a good choice when the array is nearly sorted.

How Insertion Sort Works

- ***Start with the second element:*** The first element is considered sorted.
• Compare and insert: Pick the next element and compare it with the elements in the sorted part of the array.
• Shift elements: If the current element is smaller than the compared element, shift the compared element and all elements after it one position to the right.
• Insert: Insert the current element into the empty position.
• Repeat: Repeat steps 2-4 for all remaining elements in the array.

Visual Example

Let’s sort the array [5, 2, 4, 6, 1, 3] using insertion sort:

Step 1:  The first element (5) is considered sorted.

Step 2:  Compare 2 with 5. 2 is smaller, so shift 5 to the right and insert 2 in its place.

- Array:[2, 5, 4, 6, 1, 3]

Step 3:  Compare 4 with 5. 4 is smaller, so shift 5 to the right and insert 4 in its place.

- Array:[2, 4, 5, 6, 1, 3]

Step 4:  Compare 6 with 5. 6 is larger, so it remains in its position.

- Array:[2, 4, 5, 6, 1, 3]

Step 5:  Compare 1 with 5. 1 is smaller, so shift 5, 6, and 3 to the right and insert 1 in its place.

- Array:[1, 2, 4, 5, 6, 3]

Step 6:  Compare 3 with 5. 3 is smaller, so shift 5 and 6 to the right and insert 3 in its place.

- Array:[1, 2, 3, 4, 5, 6]

The array is now sorted.

Code Implementation (Python)

def insertion_sort(arr):
  n = len(arr)

  # Traverse through 1 to n
  for i in range(1, n):
    key = arr[i]

    # Move elements of arr[0..i-1], that are
    # greater than key,    to one position ahead
    # of their current position
    j = i-1
    while j >= 0 and key < arr[j]:
        arr[j+1] = arr[j]
        j -= 1
    arr[j+1] = key

# Driver code to test above
arr    = [5, 2, 4, 6, 1, 3]
insertion_sort(arr)
print("Sorted array is:")
for i in range(len(arr)):
    print(arr[i], end=" ")

Time Complexity

- ***Best case:*** The array is already sorted. The time complexity is O(n).
• Average case: The time complexity is O(n^2).
• Worst case: The array is sorted in reverse order. The time complexity is O(n^2).

Space Complexity

The space complexity of insertion sort is O(1) as it only requires a constant amount of extra space.

Advantages of Insertion Sort

- ***Simple to implement:*** Insertion sort is easy to understand and code.
• Efficient for small datasets: It’s a good choice for small arrays.
• Online algorithm: It can process elements one at a time as they arrive.
• Stable: It preserves the relative order of elements with equal keys.

Disadvantages of Insertion Sort

- ***Inefficient for large datasets:*** It's not suitable for large arrays due to its quadratic time complexity.
• Slow for nearly sorted arrays: While it’s efficient for sorted arrays, it can be slow for nearly sorted arrays.

Conclusion

Insertion sort is a basic sorting algorithm that’s suitable for small datasets and simple applications. However, for larger datasets, more efficient algorithms like quicksort or merge sort are preferred. Understanding insertion sort is a good starting point for learning more complex sorting algorithms.