Seth.

Insertion Sort - Technical Overview

1. Algorithm Description: Insertion Sort is a simple sorting algorithm that builds a sorted array one element at a time by repeatedly taking one element from the unsorted portion and inserting it into the correct position in the sorted portion.

2. Steps of Insertion Sort:

• Start with the second element (first element is considered sorted).
• Compare the current element (key) with the elements in the sorted portion (to its left).
• Shift all larger elements in the sorted portion one position to the right to make space for the key.
• Insert the key in its correct position.
• Repeat until all elements are sorted.

3. Time Complexity: O(n²) in the worst and average case, and O(n) in the best case (when the array is already sorted).

4. Space Complexity: O(1), as it operates in-place.

5. Stability: Insertion Sort is a stable algorithm.

6. Suitability: Efficient for small datasets or nearly sorted arrays.