Insertion sort
Insertion sort is an interactive experiment in Algorithms Visualised, a free simulation from StudyFi Lab that runs right in your browser.
Insertion sort works like sorting cards in your hand: the left part is already sorted, and each next element (the key) moves left until it meets a smaller one. Larger elements shift one place to the right on the way. On random data it is O(n²), but on nearly sorted data almost O(n) — a sorted array needs only n−1 comparisons.
Try this: Run it on a nearly sorted array, then on a reversed one. How many times more shifts does the reversed array need?
Frequently asked questions
What does the “Insertion sort” experiment show?
Insertion sort works like sorting cards in your hand: the left part is already sorted, and each next element (the key) moves left until it meets a smaller one. Larger elements shift one place to the right on the way. On random data it is O(n²), but on nearly sorted data almost O(n) — a sorted array needs only n−1 comparisons.
How do I try “Insertion sort”?
Run it on a nearly sorted array, then on a reversed one. How many times more shifts does the reversed array need?
Studying for a test?
Upload your notes and StudyFi turns them into flashcards, tests and podcasts.