Insertion Sort
Insert each item into its place in the sorted part.
About this topic
Insertion sort builds a sorted list one item at a time, much like sorting playing cards in your hand. It takes the next item and inserts it into the correct position among the items already sorted, shifting larger items one place to the right.
For example, with [5, 2, 4, 1], start with 5 as sorted. Take 2 and insert before 5, giving [2, 5, 4, 1]. Take 4 and insert between 2 and 5, giving [2, 4, 5, 1]. Take 1 and shift everything right to put it first. In the worst case, such as reverse-ordered data, it takes O(n squared) time, but on nearly sorted data it is close to O(n), making it fast in that situation. It also sorts in place and is stable, keeping equal items in their original order.
Real libraries use insertion sort for small sections of data inside faster algorithms. A common mistake is overwriting an item while shifting without saving it first. Another is stopping the shifting too early or too late at the boundary. Imagine your hand of cards to check that your steps make sense.
Key ideas
- Great for nearly sorted lists
- Like sorting playing cards
- O(n²) worst case
Quick check
Use cases: where Insertion Sort helps
- Homework: review the key idea behind Insertion Sort before you start a problem set.
- Exam revision: use the quick check to test whether you can recall Insertion Sort without notes.
- Visual learning: play with the interactive lab to see how Insertion Sort changes when you adjust its inputs.
- Teaching a friend: explain Insertion Sort in your own words, then compare your version with the key ideas.
Computing ideas run phones, search engines, games and the wider internet.
Frequently asked questions
What is Insertion Sort?
Insert each item into its place in the sorted part.
What will I learn in Insertion Sort?
Great for nearly sorted lists. Like sorting playing cards. O(n²) worst case.
Is Insertion Sort part of Computer Science?
Yes. It is one of 80 Computer Science topics on LearnViz HighSchoolEdu, with 3 key ideas, a live animation and a quick check.
Does the Insertion Sort lab work on a phone or tablet?
Yes. The animation resizes to fit your screen and supports touch, so you can drag, tap and slide with your finger.
How should I study Insertion Sort?
Read the summary and key ideas first, play with the interactive lab to see the idea in motion, then answer the quick check. If you get a question wrong, go back to the key idea it tests.
Do I need an account, and is my progress saved?
No account is needed. Marking a topic as learned is saved in your own browser, so it stays on that device and is not sent to a server.