Question

How does Insertion Sort work?

Answer 1

Insertion Sort works by dividing the array into a sorted region and an unsorted region. The algorithm iteratively takes elements from the unsorted region and inserts them into their correct position in the sorted region. Here's a step-by-step explanation of how Insertion Sort works:

1. Initial State:

   • The first element in the array is considered sorted.
   • The remaining elements constitute the unsorted region.

2. Iterative Process:

   • For each unsorted element, compare it with the elements in the sorted region, moving from right to left.
   • Shift the elements in the sorted region to the right until the correct position for the current element is found.
   • Insert the current element into its correct position in the sorted region.

3. Repeat:

   • Continue this process for each element in the unsorted region until the entire array is sorted.

Let's illustrate the process with an example:

Consider the array: [5, 2, 4, 6, 1, 3]

1. Iteration 1:

   • Element 2 is compared with 5 and swapped, resulting in [2, 5, 4, 6, 1, 3].
   • Element 4 is compared with 5, 2 and inserted between them, resulting in [2, 4, 5, 6, 1, 3].

2. Iteration 2:

   • Element 1 is compared with 6, 5, 4, 2 and inserted at the beginning, resulting in [1, 2, 4, 5, 6, 3].

3. Iteration 3:

   • Element 3 is compared with 6 and inserted between 2 and 4, resulting in [1, 2, 3, 4, 5, 6].

4. Final Sorted Array:

   • The array is now sorted.

Insertion Sort is an in-place sorting algorithm, and its time complexity is O(n^2) in the worst and average cases. While not as efficient as some other sorting algorithms for large datasets, Insertion Sort performs well for small datasets or partially sorted datasets.