Understanding Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as Quick Sort, Heap Sort, or Merge Sort, but it offers several advantages.

How it works

1. Partition: The array is virtually split into a sorted and an unsorted part.
2. Select & Key: Values from the unsorted part are picked and placed at the correct position in the sorted part.
3. Shift: To insert an element, we compare it with the elements in the sorted portion from right to left. If they are larger than our key element, we shift them to the right to make space for insertion.

Mathematical Complexities

• Best Case Complexity O(N): Occurs when the array is already sorted; the inner loop does not perform any shifts.
• Worst & Average Case Complexity O(N²): Occurs when elements are reverse sorted.
• Space Complexity O(1): In-place sorting algorithm.

💡 Note: Insertion Sort is highly efficient for small data sets or datasets that are already substantially sorted, making it popular in hybrid algorithms (like Timsort, which falls back to insertion sort for small segments).