Insertion Sort
Computer Science: OCR A Level, topic 8.1.6
Insertion Sort
Insertion sort is a simple sorting algorithm, which is very intuitive.
The concept
- Imagine sorting a deck of cards.
- Hold the deck of cards in one hand, and place a single card down on the desk.
- Take a card from the top of the deck in your hand, and put it in the correct place in the other deck.
- Repeat until all the cards are gone.
In English
- Take the second card:
- Compare to the first card, swap if needed.
- Take the third card:
- Compare to second card, swap if needed.
- Compare to first card, swap if needed.
- Take the fourth card:
- Compare to all previous cards.
- Repeat for all cards.
In pseudocode
Pros and cons of insertion sort
- Pros:
- Easy to implement.
- Little memory used.
- Cons:
- Not very efficient.
Test yourself on Insertion Sort
What is the main disadvantage of insertion sort?