Insertion Sort Algorithm with Playing Cards

Being Compared
Swapped
Compared, No Swap
Sorted
Unsorted
Initial Array
5
2
8
3
6
Starting with cards: 5, 2, 8, 3, 6. The first element (5) is considered sorted.
Step 1: Insert 2
5
2
8
3
6
Compare 2 with 5. Since 2 < 5, we need to swap them.
Step 1 Result: After inserting 2
2
5
8
3
6
2 is inserted at the beginning. Now 2 and 5 are in sorted order.
Step 2: Insert 8
2
5
8
3
6
Compare 8 with 5. Since 8 > 5, no swap needed. 8 is already in correct position.
Step 2 Result: After inserting 8
2
5
8
3
6
8 stays in place. Now 2, 5, 8 are in sorted order.
Step 3: Insert 3 - Compare with 8
2
5
8
3
6
Compare 3 with 8. Since 3 < 8, swap them and continue comparing.
Step 3: After swapping 3 and 8 - Compare with 5
2
5
3
8
6
Now compare 3 with 5. Since 3 < 5, swap them and continue.
Step 3: After swapping 3 and 5 - Compare with 2
2
3
5
8
6
Compare 3 with 2. Since 3 > 2, no more swaps needed. 3 is in correct position.
Step 3 Result: After inserting 3
2
3
5
8
6
3 is inserted in correct position. Now 2, 3, 5, 8 are in sorted order.
Step 4: Insert 6 - Compare with 8
2
3
5
8
6
Compare 6 with 8. Since 6 < 8, swap them and continue comparing.
Step 4: After swapping 6 and 8 - Compare with 5
2
3
5
6
8
Compare 6 with 5. Since 6 > 5, no more swaps needed. 6 is in correct position.
Final Result: Completely Sorted
2
3
5
6
8
All cards are now in sorted order: 2, 3, 5, 6, 8. Insertion sort complete!

How Insertion Sort Works:

Insertion sort builds the final sorted array one element at a time. It takes each element from the unsorted portion and inserts it into the correct position in the sorted portion by comparing and swapping with elements to its left until it finds its proper place.

Time Complexity: O(n²) in worst case, O(n) in best case (already sorted)

Space Complexity: O(1) - sorts in place