Insertion Sort

Given an unsorted array of integers, sort it in ascending order using the Insertion Sort algorithm. Modify the array in-place ($O(1)$ extra space). Input: [12, 11, 13, 5, 6] → Output: [5, 6, 11, 12, 13]. Constraint: You must strictly use the Insertion Sort logic. Do not use built-in sort functions.

Think of sorting a hand of playing cards. You keep the sorted cards in your left hand and pick up one unsorted card at a time. You scan your sorted hand from right to left, shift the larger cards over to make room, and insert the new card into its correct position. The left side of the array is progressively built up as a fully sorted section.

1. Iterate from index $i = 1$ to $N-1$ (assume the first element at index 0 is already sorted).
2. Store the current element in a variable called item (this is the card you just picked up).
3. Use an inner loop pointer $j$ starting at $i - 1$ to scan the sorted left portion backwards.
4. While $j \ge 0$ and the element arr[j] is strictly greater than item, shift the element one position to the right (arr[j + 1] = arr[j]).
5. Once the loop stops, insert the item into the vacated spot (arr[j + 1] = item).

• Forgetting the boundary check j >= 0 in the while loop, which will cause an IndexError when scanning past the front of the array.
• Overwriting values instead of shifting them (forgetting to store arr[i] in the temporary item variable first).
• Using arr[j] >= item instead of arr[j] > item. Using >= causes the algorithm to swap identical elements, which breaks the "stability" of the sort.

Insertion Sort is highly efficient for small datasets or arrays that are already partially sorted (it is an "adaptive" algorithm). It is also a "stable" sort, meaning duplicate elements retain their original relative order. While it shares the same $O(N^2)$ worst-case time complexity as Bubble and Selection sort, its $O(N)$ best-case makes it the fastest of the three in real-world, nearly-sorted scenarios.