Insertion Sort
Insert each element into the sorted part on its left — $O(n^2)$, but $O(n)$ for nearly-sorted data.
Beginner
Used inside Timsort and introsort for small runs.
Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.
Discussion (0)
Sign in or join free to ask questions and discuss this topic.