Exploring Time and Space Complexities of Insertion Sort

Insertion sort is a comparison-based sorting algorithm that builds the sorted array one element at a time.

It works by iterating over the array, picking each element, and inserting it into the correct position relative to the already sorted portion of the array.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

template<typename T>
void insertion_sort(std::vector<T>& arr) {
    for(int i = 1; i < arr.size(); ++i) {
        T key = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Best Case Time Complexity: O(n)

The best-case time complexity occurs when the data is already sorted. Consider this data:

[4, 16, 17, 18]

In the case of sorted data, the inner loop will only run once and terminate as no shifts are made. This results in a best-case time complexity of O(n).

Worst Case Time Complexity: <katex>O(n^{2})</katex>

The worst-case time complexity occurs when the input data is in reverse order. Consider another set of data:

[18, 17, 16, 4]

When the data is in reverse order, each element is farthest from its correct position. So, two nested loops perform pairwise comparisons and shifts for each element.

Therefore, the time complexity becomes <katex>O(n^{2})</katex>.

Average Case Time Complexity: <katex>O(n^{2})</katex>

In the average case, the elements are in random order. For example,

[17, 18, 4, 16]

In this case, the algorithm needs to shift almost half of the elements while it performs a pairwise comparison for each element.

This results in an average case time complexity of <katex>O(n^{2})</katex>.

Space Complexity of Insertion Sort: O(1)

Insertion sort is an in-place sorting algorithm. It only uses a small, fixed amount of additional memory for temporary variables like key and j.

Therefore, the space complexity is O(1).

Summary: Time and Space Complexity

When to Use Insertion Sort?

Insertion sort is a simple and memory-efficient algorithm with O(1) space complexity, making it useful in certain scenarios.

When to Use:

1. Small datasets: Insertion sort is efficient for sorting small arrays or lists because its overhead is low.
2. Nearly sorted data: If the array is nearly sorted, insertion sort can be very fast, with a best-case time complexity of O(n).

When to Avoid:

1. Large datasets: For large unsorted datasets, insertion sort becomes inefficient due to its <katex>O(n^{2})</katex> time complexity. Other algorithms like Quick Sort or Merge Sort are generally more efficient in such cases.

Here is a comparison of insertion sort's performance in different scenarios:

While the algorithm has quadratic time complexity in the worst and average cases, it performs relatively efficiently with small or nearly sorted datasets.