Insertion Sort is a simple and efficient comparison-based sorting algorithm. It builds the final sorted array one element at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort, but it performs well for small datasets or nearly sorted arrays.

Basic Implementation

function insertionSort(arr: number[]): number[] {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    const currentElement = arr[i];
    let j = i - 1;
    // Move elements greater than currentElement to the right
    while (j >= 0 && arr[j] > currentElement) {
      arr[j + 1] = arr[j];
      j--;
    }
    // Insert currentElement into its correct position
    arr[j + 1] = currentElement;
  }
  return arr;
}

How Insertion Sort Works

• The algorithm starts with a single element (considered a sorted subarray).

• It iterates through the remaining unsorted elements, repeatedly inserting each element into its correct position within the sorted subarray.

• The sorted subarray grows with each iteration until the entire array is sorted.

Time Complexity

The time complexity of Insertion Sort is O(n^2), where 'n' is the number of elements in the array. In the worst case, each element must be compared and shifted to its correct position in the sorted subarray.

Space Complexity

Insertion Sort has a space complexity of O(1) since it only uses a constant amount of additional memory for variables like currentElement and j.

Advantages of Insertion Sort

• Insertion Sort is easy to understand and implement, making it suitable for educational purposes.

• It performs well for small datasets or nearly sorted arrays, outperforming more complex algorithms in these scenarios.

Limitations of Insertion Sort

• Insertion Sort becomes inefficient for large datasets due to its quadratic time complexity.

• While it is an in-place sorting algorithm, it is not stable, meaning the relative order of equal elements may not be preserved.

When to Use Insertion Sort

Insertion Sort is suitable for small datasets or situations where simplicity is more critical than efficiency. It is often used in practice when the dataset is nearly sorted, as it can perform well in such scenarios.

Conclusion

Insertion Sort provides a clear introduction to the concept of sorting algorithms and in-place sorting. While not the most efficient algorithm for large datasets, understanding how it works and its principles is valuable for learning about sorting techniques and algorithms in general.