Problem: Insertion Sort

Insertion Sort is a simple and intuitive sorting algorithm that builds the final sorted array one element at a time. It is particularly efficient for small or nearly sorted datasets.

---

How It Works

1. Initialization
   Assume the first element of the array is already sorted.
2. Iteration
   Starting from the second element, pick the current element (key) and compare it with the elements in the sorted portion (to its left).
3. Shifting Elements
   Shift all elements in the sorted section that are greater than the key one position to the right.
4. Insertion
   Insert the key into its correct position in the sorted section.
5. Repeat
   Repeat the process for each element until the entire array is sorted.

---

Pseudocode

for i = 1 to length(array) - 1:
    key = array[i]
    j = i - 1

    while j >= 0 and array[j] > key:
        array[j + 1] = array[j]
        j = j - 1

    array[j + 1] = key

Time Complexity

• Best Case: O(n) when the array is already sorted.
• Average/Worst Case: O(n²) due to the nested loop in the worst scenario.