Insertion Sort Algorithm

Insertion Sort Algorithm

Insertion Sort is a simple comparison-based sorting algorithm that builds the final sorted array one element at a time. It works much like how people sort playing cards in their hands: we pick up one card at a time and insert it into its correct position in the already sorted portion of the deck.

How Insertion Sort Works

The array is divided into two portions:

1. A sorted portion at the beginning of the array.
2. An unsorted portion at the end of the array.

In each iteration, Insertion Sort:

• Takes the first unsorted element.
• Compares it with the elements in the sorted portion.
• Inserts it into the correct position by shifting the larger elements to the right.

Steps of the Algorithm:

1. Start with the second element (index 1), assuming the first element (index 0) is already sorted.
2. Compare the current element with the element to its left.
3. If the current element is smaller, shift the elements of the sorted portion to the right until the correct position for the current element is found.
4. Insert the current element at the correct position.
5. Move to the next element in the unsorted portion and repeat the process.
6. Continue this process until all elements are sorted.

Pseudocode:

for i = 1 to n-1  // Loop through the unsorted part of the array
    key = array[i]  // The element to be inserted into the sorted portion
    j = i - 1  // Pointer to the last element in the sorted portion
    // Shift elements of the sorted portion that are greater than key
    while j >= 0 and array[j] > key
        array[j + 1] = array[j]  // Shift element one position to the right
        j = j - 1  // Move to the next element in the sorted portion
    array[j + 1] = key  // Insert the key into the correct position

Example Walkthrough of Insertion Sort

Let’s take an example and walk through how Insertion Sort works.

Suppose we have the following unsorted array:

[12, 11, 13, 5, 6]

Initial Array:

[12, 11, 13, 5, 6]

First Pass (i = 1):

• The current element is 11 (key = 11).
• Compare 11 with 12 (element at index 0). Since 12 is greater than 11, shift 12 one position to the right.
• Insert 11 in position 0.

Array after the first pass:

[11, 12, 13, 5, 6]

Second Pass (i = 2):

• The current element is 13 (key = 13).
• Compare 13 with 12 (element at index 1). Since 13 is greater than 12, no shifting is needed, and 13 remains in its current position.

Array after the second pass:

[11, 12, 13, 5, 6]

Third Pass (i = 3):

• The current element is 5 (key = 5).
• Compare 5 with 13 (element at index 2). Since 13 is greater, shift 13 to the right.
• Compare 5 with 12 (element at index 1). Since 12 is greater, shift 12 to the right.
• Compare 5 with 11 (element at index 0). Since 11 is greater, shift 11 to the right.
• Insert 5 in position 0.

Array after the third pass:

[5, 11, 12, 13, 6]

Fourth Pass (i = 4):

• The current element is 6 (key = 6).
• Compare 6 with 13 (element at index 3). Since 13 is greater, shift 13 to the right.
• Compare 6 with 12 (element at index 2). Since 12 is greater, shift 12 to the right.
• Compare 6 with 11 (element at index 1). Since 11 is greater, shift 11 to the right.
• Insert 6 in position 1.

Array after the fourth pass:

[5, 6, 11, 12, 13]

Now the array is sorted.

Time Complexity of Insertion Sort

Let’s analyze the time complexity of Insertion Sort:

Best Case (Array is already sorted):

• In this case, each element is greater than or equal to the one before it, so no shifting is required.
• The inner loop runs only once for each element to compare it to the previous one, resulting in a time complexity of:
  • Best Case Time Complexity: O(n).

Worst Case (Array is sorted in reverse order):

• In the worst case, each element has to be compared to all the other elements in the sorted portion. For each element, the number of comparisons increases linearly.

• The inner loop runs i times for each i in the outer loop, leading to a total number of comparisons of:

  $$(n - 1) + (n - 2) + (n - 3) + \ldots + 1 = \frac{n(n - 1)}{2} = O(n^2)$$

• Worst Case Time Complexity: O(n²).

Average Case:

• On average, the algorithm needs to make about half the comparisons for each element. Thus, the time complexity is still O(n²) because the total comparisons are still proportional to $\frac{n(n - 1)}{2}$.

Summary of Time Complexity:

• Best Case: O(n) (already sorted array).
• Average Case: O(n²) (random array).
• Worst Case: O(n²) (array sorted in reverse order).

Space Complexity:

• Space Complexity: O(1) (in-place sorting)
  • Insertion Sort only requires a constant amount of extra space (just a few variables for tracking the current element and the position for insertion).
  • The sorting is done within the original array itself.

---

Advantages of Insertion Sort

1. Simple to Implement: Insertion Sort is easy to understand and implement.
2. In-place Sorting: It does not require additional memory outside of the input array.
3. Efficient for Small Arrays: For small arrays or nearly sorted data, Insertion Sort is very efficient because of its O(n) time complexity in the best case.
4. Stable: It is a stable sorting algorithm, meaning that the relative order of equal elements is preserved.
5. Adaptive: Insertion Sort performs better when the array is already partially sorted, as the number of comparisons and shifts decreases.

---

Disadvantages of Insertion Sort

1. Inefficient for Large Arrays: The time complexity of O(n²) makes it inefficient for large datasets compared to more advanced algorithms like Quick Sort, Merge Sort, or Heap Sort.
2. Not Suitable for Large Data: Due to its quadratic time complexity, Insertion Sort becomes slower as the input size grows.
3. Non-parallelizable: Like most comparison-based algorithms, it does not lend itself well to parallelization, limiting its scalability.

---

Conclusion

Insertion Sort is a simple and intuitive algorithm that performs well for small or partially sorted datasets. It is often used as a subroutine in more complex algorithms like Timsort (used in Python's built-in sort function) or when sorting small arrays where the overhead of more complex algorithms is unnecessary. However, for larger datasets, more efficient algorithms like Merge Sort, Quick Sort, or Heap Sort are generally preferred.