Insertion Sort

Insertion Sort is a sorting algorithm that operates in a way similar to the process by which many people sort cards in their hands during a game. It simply takes one element at a time and inserts it into the correct position within the already sorted list, moving all subsequent elements.

How it works

The functioning of the algorithm can be summarized in the following steps:

1. It starts from the second element (index 1 in zero-based array), considering the first element as already sorted.
2. It takes the current element and compares it with all preceding elements in the array.
3. If the current element is smaller than its predecessor, it swaps the two elements and continues to compare with all other preceding elements.
4. This process continues until the current element is larger than its predecessor or until it reaches the beginning of the array, indicating that the current element is the smallest in the array up to that point.
5. It moves on to the next element in the array and repeats the process until all the elements in the array have been sorted.

Here is a simple implementation in C#:

public void InsertionSort(int[] arr)
{
    var len = arr.Length;

    for (var i = 1; i < len; i++)
    {
        var key = arr[i];
        var j = i - 1;

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

        arr[j + 1] = key;
    }
}

Time complexity

In the worst case and average case, the time complexity is O(n²), where n is the number of elements in the array. This means that the execution time increases quadratically with the size of the input. However, in the best case (when the array is already sorted), it has a time complexity of O(n).

Space complexity

Being an in-place sorting algorithm, its space complexity is O(1), meaning that memory usage does not increase with input size. Simply put, it does not require additional space to sort the data.

Conclusion

Insertion Sort is an excellent example of the variety of sorting algorithms. Although it may not excel in large data set situations because of its quadratic time complexity, its unique strengths certainly shine in particular scenarios.

First, its simplicity in terms of understanding and implementation makes it an excellent teaching tool for those new to the world of algorithms.

Second, when dealing with small data sets or near-sorted data sets, Insertion Sort can be surprisingly efficient and even outperform more complex algorithms.

Third, its stability-the property of preserving the relative order of equal elements-and its in-place nature are advantageous in certain situations.

Finally, sorting by insertion performs exceptionally well when data is received in real time. It can maintain an ordered list as new items are inserted, making it an excellent choice for scenarios where it is useful to have a continuously ordered view of the data.

References

• Algoritmi e programmazione in C di Francesco Oliveri, Aracne editrice (Italian book)