What is Insertion Sort?

Insertion Sort is a comparison-based sorting algorithm where elements are moved one by one to their correct position in a growing sorted portion of the array.

Insertion Sort Steps

Step-by-Step Process:
  1. Start from the second element, treating the first element as sorted.
  2. For each element, find its correct position within the sorted portion by shifting larger elements to the right.

Insertion Sort Example

Example:

Array before sorting: [5, 3, 8, 4, 2]

  1. Insert 3: [3, 5, 8, 4, 2]
  2. Insert 4: [3, 4, 5, 8, 2]
  3. Insert 2: [2, 3, 4, 5, 8]

Time and Space Complexity

Time Complexity:

  1. Worst Case: O(n²) - occurs when the array is in reverse order.
  2. Best Case: O(n) - occurs when the array is already sorted.
  3. Average Case: O(n²) - for random order of elements.

Space Complexity: O(1) - only requires a constant amount of additional space.

Pseudo Code for Insertion Sort

The following is the pseudo code for Insertion Sort:

Begin
  for i = 1 to n-1
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key
      arr[j + 1] = arr[j]
      j = j - 1
    arr[j + 1] = key
End

Insertion Sort Visualization

for (int i = 1; i < n; i++) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j = j - 1;
    }
    arr[j + 1] = key;
}
Home