Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It's much like how you sort playing cards in your hands. We begin with an empty left hand. You start with an unsorted hand, remove one card at a time from (from the unsorted pile) and insert them in the correct position in the left hand (sorted array).
How It Works
Start from the second element (index 1). [one element is already sorted]
Compare the current element with the elements before it.
Move greater elements ahead to make space for the current element. (SHIFT) All the greater elements are moved one space to the RIGHT.
Insert the current element at its correct position. (INSERT)
Repeat for all elements.
Step-by-Step Example
Let's sort the array [5, 2, 4, 6, 1, 3].
Initial Array: [5, 2, 4, 6, 1, 3]
Step 1: i = 1 (key = 2)
Compare 2 with 5. Since 2 < 5, shift 5 to the right.
Insert 2 at position 0.
Array: [2, 5, 4, 6, 1, 3]
Step 2: i = 2 (key = 4)
Compare 4 with 5. Since 4 < 5, shift 5 to right.
Compare 4 with 2. Since 4 > 2, stop.
Insert 4 at position 1.
Array: [2, 4, 5, 6, 1, 3]
Step 3: i = 3 (key = 6)
6 > 5, no shifting needed.
Insert 6 at position 3.
Array: [2, 4, 5, 6, 1, 3]
Step 4: i = 4 (key = 1)
Compare 1 with 6: shift 6 to right. ()
Compare 1 with 5: shift 5 to right.
Compare 1 with 4: shift 4 to right.
Compare 1 with 2: shift 2 to right.
Insert 1 at position 0.
Array: [1, 2, 4, 5, 6, 3]
Step 5: i = 5 (key = 3)
Compare 3 with 6: shift 6 to right.
Compare 3 with 5: shift 5 to right.
Compare 3 with 4: shift 4 to right.
Compare 3 with 2: stop (3 > 2).
Insert 3 at position 2.
Array: [1, 2, 3, 4, 5, 6]
The left hand side array, till i at any given time is sorted.
