Insertion Sort is a simple and intuitive sorting algorithm, ideal for small or nearly sorted datasets. It sorts the array one element at a time by inserting each element into its correct position among the previously sorted elements.
How Insertion Sort Works
Assume the first element is "already sorted".
Take the next (unsorted) element.
Compare it with elements in the sorted part (to its left) and move larger elements one position to the right.
Insert the unsorted element in its correct position.
Repeat until the whole array is sorted.
Example
Unsorted list: [5, 3, 8, 4, 2]
Let’s sort step by step:
Pass 1:
Sorted part: [5]
Unsorted part: [3, 8, 4, 2]
Take 3. Compare with 5: 3 < 5
Shift 5 right: [5, 5, 8, 4, 2]
Place 3 at position 0: [3, 5, 8, 4, 2]
Pass 2:
Sorted part: [3, 5]
Take 8.
8 > 5, so leave it: [3, 5, 8, 4, 2]
Pass 3:
Sorted part: [3, 5, 8]
Take 4.
Compare with 8: 4 < 8, shift 8 right.
Compare with 5: 4 < 5, shift 5 right.
Compare with 3: 4 > 3, so insert 4 after 3.
After shifting: [3, 4, 5, 8, 2]
Pass 4:
Sorted part: [3, 4, 5, 8]
Take 2.
Compare with 8: shift 8 right.
Compare with 5: shift 5 right.
Compare with 4: shift 4 right.
Compare with 3: shift 3 right.
Insert 2 at the start: [2, 3, 4, 5, 8]
Now the list is sorted!
Key Points:
Time Complexity: O(n²) in worst case, but efficient (O(n)) for nearly sorted arrays
Stable sort (does not change the order of equal keys)
In-place (does not use extra space)
Good for small or partially sorted datasets
In summary: Insertion Sort builds the final sorted array one item at a time, inserting each element into the correct position among the previously sorted elements. Think of the way you sort playing cards in your hand: you pick one card at a time and insert it into the right spot among the cards already in your hand.
