19. Insertion Sort: Concept and Implementation (O(N²))

Insertion Sort is often compared to sorting a hand of playing cards. It is highly efficient for small arrays or nearly sorted arrays.

Concept

It iterates through the array, taking one element at a time (the 'key') and inserting it into its correct position within the already sorted portion of the array.

Implementation Steps

1. Start with the second element (assume the first is sorted).
2. Take this element (the key).
3. Shift elements in the sorted portion that are greater than the key one position to the right.
4. Insert the key into the open spot.

python def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 # Move elements of arr[0..i-1], that are greater than key, # to one position ahead of their current position while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr