Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It repeatedly takes an unsorted element and inserts it into its correct position within the sorted part of the array. This process continues until the entire array is sorted. It has a time complexity of O(n^2) but is efficient for small datasets or partially sorted data.

Here’s how the Insertion sort algorithm works step by step:

  1. Initialization: Start with the first element in the list (considered as the sorted portion) and the second element as the first element in the unsorted portion.
  2. Comparing and Inserting: Compare the first element in the unsorted portion with the elements in the sorted portion. Move from right to left in the sorted portion until you find the correct position for the current unsorted element.
  3. Shifting: While comparing and moving elements in the sorted portion, if you find an element in the sorted portion that is greater (for ascending order sorting) than the current unsorted element, shift that element one position to the right.
  4. Insertion: Once you find the correct position in the sorted portion for the current unsorted element, insert the unsorted element into that position.
  5. Repeat: Continue this process for the remaining unsorted elements, one element at a time. In each iteration, the sorted portion of the list grows, and the unsorted portion shrinks.
  6. Termination: The algorithm terminates when all elements are in their correct sorted positions.

Understanding Insertion Sort with an Example

Insertion sort repeatedly takes one element from the unsorted portion and inserts it into the correct position within the sorted portion, gradually building the sorted list.

Example -1 Unsorted List: [23, 67, 45, 89, 12, 56]

Step 1:

  • Start with the first element, 23, considered as the sorted portion.
  • Take the second element, 67, as the current unsorted element.
  • Compare 67 with 23. Since 67 is greater, no shift is needed.

Result: [23, 67, 45, 89, 12, 56]

Step 2:

  • Move to the third element, 45, as the current unsorted element.
  • Compare 45 with 67. Since 45 is smaller, shift 67 to the right.

Result: [23, 45, 67, 89, 12, 56]

Step 3:

  • Move to the fourth element, 89, as the current unsorted element.
  • Compare 89 with 67. Since 89 is greater, no shift is needed.

Result: [23, 45, 67, 89, 12, 56]

Step 4:

  • Move to the fifth element, 12, as the current unsorted element.
  • Compare 12 with 89. Since 12 is smaller, shift 89 to the right.
  • Compare 12 with 67. Since 12 is smaller, shift 67 to the right.
  • Compare 12 with 45. Since 12 is smaller, shift 45 to the right.

Result: [12, 23, 45, 67, 89, 56]

Step 5:

  • Move to the last element, 56, as the current unsorted element.
  • Compare 56 with 89. Since 56 is smaller, shift 89 to the right.
  • Compare 56 with 67. Since 56 is smaller, shift 67 to the right.

Result: [12, 23, 45, 56, 67, 89]

Now, the entire list is sorted in ascending order:

Sorted List: [12, 23, 45, 56, 67, 89]

Example -2 Unsorted List: [3, 7, 4, 8, 12, 16]

Step 1:

  • Start with the first element, 3, considered as the sorted portion.
  • Take the second element, 7, as the current unsorted element.
  • Compare 7 with 3. Since 7 is greater, no shift is needed.

Result: [3, 7, 4, 8, 12, 16]

Step 2:

  • Move to the third element, 4, as the current unsorted element.
  • Compare 4 with 7. Since 4 is smaller, shift 7 to the right.

Result: [3, 4, 7, 8, 12, 16]

Step 3:

  • Move to the fourth element, 8, as the current unsorted element.
  • Compare 8 with 7. Since 8 is greater, no shift is needed.

Result: [3, 4, 7, 8, 12, 16]

Step 4:

  • Move to the fifth element, 12, as the current unsorted element.
  • Compare 12 with 8. Since 12 is greater, no shift is needed.

Result: [3, 4, 7, 8, 12, 16]

Step 5:

  • Move to the last element, 16, as the current unsorted element.
  • Compare 16 with 12. Since 16 is greater, no shift is needed.

Result: [3, 4, 7, 8, 12, 16]

Now, the entire list is sorted in ascending order:

Sorted List: [3, 4, 7, 8, 12, 16]

Python Code of the Insertion sort

Situations where insertion sort can be a good choice:

  1. Small Datasets: Insertion sort is very efficient for sorting small lists or arrays. When the number of elements to be sorted is relatively small (typically fewer than 20-30 elements), insertion sort’s simplicity and low overhead can make it faster than more complex sorting algorithms.
  2. Partially Sorted Data: If you have a dataset where a significant portion of the elements are already in the correct order or nearly sorted, insertion sort performs exceptionally well. In such cases, it has a linear time complexity, O(n), for sorting nearly sorted data.
  3. Stable Sorting: If you need a sorting algorithm that maintains the relative order of equal elements (i.e., a stable sort), insertion sort is a stable sorting algorithm. It won’t change the order of equal elements during the sorting process.
  4. Online Sorting: Insertion sort can be used in situations where data arrives incrementally (online sorting). You can insert each new element into the sorted portion of the list as it arrives, and the list remains sorted.

In summary, insertion sort is a useful sorting algorithm for small datasets, partially sorted data, or when you need a stable sorting algorithm. Its simplicity and stability make it a good choice for certain scenarios, but for large datasets or random data, more efficient algorithms should be considered.