Insertion Sort

Code

C language code:

#include <stdio.h>

void insertion_sort(int arr[], int n) {
    int i, j, key;
    for (i = 2; i <= n; i++) {  // Start from the second element
        key = arr[i];
        for (j = i - 1; arr[j] > key; j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {-1000000, 12, 11, 13, 5, 6};  // Use a very small value as sentinel; the first element will not be sorted
    int n = sizeof(arr)/sizeof(arr[0]) - 1;  // Calculate effective length (excluding sentinel)
    
    insertion_sort(arr, n);

    printf("Sorted array: ");
    for (int i = 1; i <= n; i++) {  // Print from the first actual element
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

Code Explanation

1. Initialization: The first element of array arr, -1000000, serves as a sentinel for boundary checking. The sorting starts from the second element.
2. Main sorting loop:
   • Starts from the second element (index 2), storing the current element in key each time.
   • The inner for loop traverses backward from the position before the current element; if the current element is greater than key, it shifts the element one position backward until the correct position for inserting key is found.
3. Result output: After sorting is complete, the sorted array is printed, ignoring the first sentinel element.

Example Run

Assuming the input array is {-1000000, 12, 11, 13, 5, 6}:

1. Initial state: {-1000000, 12, 11, 13, 5, 6}
2. Insert 11: {-1000000, 11, 12, 13, 5, 6}
3. Insert 13: {-1000000, 11, 12, 13, 5, 6}
4. Insert 5: {-1000000, 5, 11, 12, 13, 6}
5. Insert 6: {-1000000, 5, 6, 11, 12, 13}

Final result: {5, 6, 11, 12, 13}

Time Complexity Analysis

The time complexity of insertion sort mainly depends on the initial order of the array.

• Best-case time complexity: When the input array is already sorted, insertion sort only needs $O(n)$ comparisons, giving a time complexity of $O(n)$.
• Worst-case time complexity: When the input array is in reverse order, insertion sort requires the maximum number of comparisons and moves, giving a time complexity of $O(n^2)$.
• Average time complexity: In general cases, the time complexity of insertion sort is $O(n^2)$.

Space Complexity Analysis

Insertion sort is an in-place sorting algorithm that requires no additional auxiliary space, with a space complexity of $O(1)$. In this implementation, we only use a few extra variables (i, j, key), so the space complexity remains at a constant level.

Advantages and Disadvantages

Advantages:

• Simple and easy to implement.
• Performs well on small datasets.
• Stable sorting algorithm; does not change the relative order of equal elements.
• In-place sorting; low space complexity.

Disadvantages:

• High time complexity for large datasets; not suitable for processing large amounts of data.

Applicable Scenarios

Insertion sort is suitable for the following scenarios:

• Sorting small datasets.
• When the array is partially sorted, insertion sort is more efficient.
• When a simple and stable sorting algorithm is needed.

Summary

Insertion sort is a simple and intuitive sorting algorithm. Although its worst-case time complexity is high, it still has advantages in specific scenarios, especially for small or partially sorted datasets. Using a sentinel element can reduce boundary checks and improve the algorithm's efficiency.