A comparison sort that builds a sorted portion of the list one element at a time, inserting each new element into its correct place among the elements already sorted; quadratic in general but fast in practice on small or nearly sorted inputs.
Facts
Time ComplexityO(n^2) in the worst case 1 Connections
Sources
1. Wikipedia, Insertion sort
Best, worst, and average casesQuote, Best, worst, and average cases
This gives insertion sort a quadratic running time (i.e., O(n2)).
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.