Glossary · Phase 7 · Software engineering
Insertion sort
Sorting like a hand of cards: slide each item left past the bigger ones until it fits. Fast on nearly sorted data.
Try it now
Each pass throws away half of what's left. Watch low and high close in.
Learn it properly
Searching, sorting and dynamic programming · The classic algorithms, and the ideas behind them. About 45 minutes.
Other terms from the same lesson
- binary search: Finding an item in a sorted list by checking the middle and throwing away the half it can't be in, again and again.
- dynamic programming: Solving a problem by filling in a table of answers to smaller, overlapping versions of it.
- memoization: Saving a function's results so a repeat call with the same input returns instantly.
- quicksort: A fast sort that splits items around a chosen pivot and sorts each side the same way, inside the list itself.
- worst case: How an algorithm behaves on its least (or most) favorable input, which can be far from its usual speed.
Never trained an AI?
Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account.