Insertion Sort Algorithm

Insertion Sort is a straightforward and efficient comparison-based sorting algorithm. The algorithm works similarly to how you might sort playing cards in your hands. It builds the sorted array one item at a time by taking each element from the unsorted portion and inserting it into its correct position in the sorted portion. This involves shifting elements in the sorted portion to the right to make space for the new element. The process starts with the second element and continues until all elements are sorted.

While Insertion Sort is not as efficient on large lists as more advanced algorithms like Quick Sort, Heap Sort or Merge Sort, it is more efficient in practice compared to other simple quadratic algorithms like Selection Sort or Bubble Sort, especially for small datasets or nearly sorted arrays.

Implementation of Insertion Sort

// Time Complexity: O(n*n) (where n = size of the array)
// for the worst and average cases &
// O(n) for the best case.
// Space Complexity: O(1)

void insertionSort(int arr[], int n)
{
    for (int i = 1; i <= n - 1; i++)
    {
        int key = arr[i];
        int j = i - 1;

        while (arr[j] > key && j >= 0)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Logic:

1. Outer Loop: Iterate from the second element to the last element of the array.

2. Key Element: Select the current element as the key element.

3. Inner Loop: Compare the key element with the elements in the sorted portion of the array (to its left) and shift the elements one position to the right until the correct position for the key element is found.

4. Insertion: Insert the key element in its correct position.

Time Complexity:

• Worst and Average Cases: O(n²)

• Best Case: O(n) when the array is already sorted

Space Complexity: O(1)

• Explanation: The algorithm sorts in place and uses a constant amount of extra space.

Example

Input: arr = [13, 46, 24, 50, 20, 9], n = 6

Output: arr = [9, 13, 20, 24, 46, 50]

Explanation: The algorithm iteratively takes an element from the unsorted portion and inserts it into the correct position in the sorted portion.

---

Step-by-Step Explanation

Let's break down the steps for the example input arr = [13, 46, 24, 50, 20, 9] using Insertion Sort:

1. Initial Array: [13, 46, 24, 50, 20, 9]

2. Pass 1:

• Array at the start of Pass 1: [13, 46, 24, 50, 20, 9]

• Key = 46, Compare with 13: No change

• Array after pass 1: [13, 46, 24, 50, 20, 9]

3. Pass 2:

• Array at the start of Pass 2: [13, 46, 24, 50, 20, 9]

• Key = 24, Compare with 46: Shift 46

• Key = 24, Compare with 13: Insert 24 after 13

• Array after pass 2: [13, 24, 46, 50, 20, 9]

4. Pass 3:

• Array at the start of Pass 3: [13, 24, 46, 50, 20, 9]

• Key = 50, Compare with 46: No change

• Array after pass 3: [13, 24, 46, 50, 20, 9]

5. Pass 4:

• Array at the start of Pass 4: [13, 24, 46, 50, 20, 9]

• Key = 20, Compare with 50: Shift 50

• Key = 20, Compare with 46: Shift 46

• Key = 20, Compare with 24: Shift 24

• Key = 20, Compare with 13: Insert 20 after 13

• Array after pass 4: [13, 20, 24, 46, 50, 9]

6. Pass 5:

• Array at the start of Pass 5: [13, 20, 24, 46, 50, 9]

• Key = 9, Compare with 50: Shift 50

• Key = 9, Compare with 46: Shift 46

• Key = 9, Compare with 24: Shift 24

• Key = 9, Compare with 20: Shift 20

• Key = 9, Compare with 13: Insert 9 at the start

• Array after pass 5: [9, 13, 20, 24, 46, 50]

7. Final Sorted Array: [9, 13, 20, 24, 46, 50]

Visualization

---

Edge Cases

• Already Sorted Array: The algorithm performs O(n) comparisons, making it efficient for nearly sorted inputs.

• Array with Identical Elements: Handles duplicates correctly without additional operations.

• Single Element Array: No changes needed, the array remains unchanged.

Additional Notes

• Efficiency: More efficient than Bubble Sort and Selection Sort for small datasets or nearly sorted arrays.

• Stability: Insertion Sort is stable, meaning it maintains the relative order of elements with equal keys.

• Use Case: Useful for small datasets, nearly sorted arrays or as a part of more complex algorithms like Tim Sort.

Conclusion

Insertion Sort is a simple yet efficient sorting algorithm for small or nearly sorted datasets. It builds the sorted array one element at a time by shifting elements as necessary to make space for the new element. Despite its quadratic time complexity for larger arrays, its stability and efficiency for small datasets make it a valuable tool for specific use cases. Its in-place sorting capability and simplicity are its main advantages.

---