Insertion Sort

Insertion Sort is a straightforward sorting algorithm that organizes a list or array by building a sorted portion one item at a time. Each element is "inserted" into its correct position relative to already sorted elements, much like sorting a hand of playing cards. While it is not the most efficient sorting algorithm for large datasets, it performs well on small, nearly sorted, or simple lists, making it a fundamental concept in sorting.

---

How Insertion Sort Works

The main idea behind Insertion Sort can be visualized by sorting playing cards:

• 1. Start with the First Element: Assume the first element is sorted.
• 2. Pick the Next Element: Move to the next unsorted element.
• 3. Shift and Insert: Shift the sorted elements to the right as needed to make space for the new element and insert it in the correct position.
• 4. Repeat: Continue picking and inserting each element until all elements are sorted.

Example of Insertion Sort

To understand this better, let’s walk through sorting the array [5, 2, 9, 1, 5, 6]:

• Initial Array: [5, 2, 9, 1, 5, 6]
• Step 1: Consider the first element (5) as sorted. Move to the second element (2).
  • Compare 2 with 5. Since 2 is smaller, shift 5 to the right.
  • Insert 2 at the beginning.
  • Array after Step 1: [2, 5, 9, 1, 5, 6]
• Step 2: Move to the third element (9).
  • Since 9 is larger than the previous elements, no shifts are necessary.
  • Array remains: [2, 5, 9, 1, 5, 6]
• Step 3: Move to the fourth element (1).
  • Shift 9, 5, and 2 one position to the right.
  • Insert 1 at the beginning.
  • Array after Step 3: [1, 2, 5, 9, 5, 6]
• Step 4: Move to the fifth element (5).
  • Shift 9 to the right and insert 5.
  • Array after Step 4: [1, 2, 5, 5, 9, 6]
• Step 5: Move to the sixth element (6).
  • Shift 9 to the right and insert 6.
  • Array after Step 5: [1, 2, 5, 5, 6, 9]
• The array is now fully sorted: [1, 2, 5, 5, 6, 9]

---

Pseudocode for Insertion Sort

Here is the pseudocode for Insertion Sort:

InsertionSort(arr):
    for i from 1 to arr.length - 1 do:
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key do:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key

Explanation of the Pseudocode

• Loop Through Each Element: Begin with the second element (index 1), assuming the first element is already sorted.
• Set the Key: Define the current element as the key that will be inserted into the sorted portion.
• Shift Larger Elements: Move all elements that are larger than key one position to the right.
• Insert the Key: Insert the key into its correct position in the sorted portion.

---

Complexity Analysis

• Time Complexity:
  • Best Case: \( O(n) \) when the list is already sorted.
  • Worst Case: \( O(n^2) \) when the list is sorted in reverse order.
  • Average Case: \( O(n^2) \), as each insertion may require shifting elements.
• Space Complexity: \( O(1) \), because Insertion Sort operates in place and requires no extra memory for sorting.

---

Advantages and Disadvantages of Insertion Sort

Advantages

• Simple to Implement: Insertion Sort is easy to code and understand, making it ideal for beginners.
• Efficient for Small Data Sets: Performs well on small arrays or lists.
• Stable Sorting Algorithm: Maintains the relative order of elements with equal values.
• Adaptive: If the list is already partially sorted, Insertion Sort can be very fast.

Disadvantages

• Inefficient on Large Data Sets: Due to its \( O(n^2) \) time complexity, Insertion Sort is unsuitable for large datasets.
• High Number of Shifts: For each insertion, the elements to the right of the key may need to be shifted, which can slow down the sorting process.

---

Step-by-Step Walkthrough with the Example Array

To further illustrate Insertion Sort, let’s go over each insertion and shift in the array [5, 2, 9, 1, 5, 6]:

• Step 1:
  • Start with index 1, where 2 is located.
  • Compare 2 with 5. Since 2 is less than 5, shift 5 one position to the right.
  • Insert 2 at index 0.
  • Result: [2, 5, 9, 1, 5, 6]
• Step 2:
  • Move to index 2 with 9.
  • Since 9 is larger than 5, no shifts are needed.
  • Result: [2, 5, 9, 1, 5, 6]
• Step 3:
  • Move to index 3 with 1.
  • Shift 9, 5, and 2 one position to the right.
  • Insert 1 at index 0.
  • Result: [1, 2, 5, 9, 5, 6]
• Step 4:
  • Move to index 4 with 5.
  • Shift 9 one position to the right and insert 5.
  • Result: [1, 2, 5, 5, 9, 6]
• Step 5:
  • Move to index 5 with 6.
  • Shift 9 one position to the right and insert 6.
  • Final sorted array: [1, 2, 5, 5, 6, 9]

---

Conclusion

Insertion Sort is an easy-to-understand sorting algorithm, particularly useful for small datasets and nearly sorted lists. While not as efficient as other sorting algorithms for large datasets, its simplicity, stability, and adaptability make it a valuable tool in specific scenarios. For instance, it is often integrated as part of more advanced sorting algorithms to handle small partitions. In summary, Insertion Sort is a foundational algorithm worth learning due to its simplicity and applications in various contexts.