Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It works by repeatedly taking an element from the unsorted part of the array and inserting it into its correct position within the sorted part of the array.

Here's the step-by-step explanation of how insertion sort works:

1. Start with the first element as the sorted portion (considering a single element as sorted array).
2. Iterate through the unsorted portion of the array, comparing each element with the elements in the sorted portion.
3. Move elements in the sorted portion that are greater than the current element to the right, creating space for the current element.
4. Insert the current element into the correct position in the sorted portion.
5. Repeat steps 2-4 until the entire array is sorted.

Code

#include <iostream>
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // Move elements of arr[0..i-1] that are greater than key
        // to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

Complexity

Worst-case time complexity (O(n^2))

The worst-case scenario occurs when the input array is in reverse order, meaning that each element must be compared and moved to its correct position within the sorted portion. In this case, the number of comparisons and swaps is approximately (n^2)/2, leading to a quadratic time complexity.

Average-case time complexity (O(n^2))

The average-case time complexity is also O(n^2). This is because insertion sort's performance is heavily influenced by the initial order of the elements. On average, it will require about (n^2)/4 comparisons and swaps.

Best-case time complexity (O(n))

The best-case scenario occurs when the input array is already sorted. In this case, no elements need to be moved, but each element still needs to be compared with the previous elements in the sorted portion to confirm its position. This results in a linear time complexity of O(n).

Space Complexity

The auxiliary space complexity of Insertion sort is O(1).