Insertion Sort
Computer Science: OCR GCSE, topic 2.1.15
Insertion Sort
Insertion sort is a simple sorting algorithm, which is very intuitive.
The concept
- Imagine sorting a deck of cards.
- You'll keep all the sorted cards at the top of the deck, take the next unsorted card and compare it with all the sorted ones from the front until you find the correct place to insert it.
In English
- Always assume the first card is sorted, since there are no other values to compare it to.
- Take the second card and compare it to the one on top. Swap if needed.
- Take the third card. Compare it with the one on top, then with the second one. Insert it in the correct place.
- Take the fourth card. Compare it with the one on top, then with the second one, then with the third one. Insert it in the correct place.
- Repeat until you have sorted all cards.
