Time ComplexityLesson 47Free preview

Insertion Sort

This lesson is part of DSA · All levels

Summary

Insertion sort has O(n) at best because each element is fairly compared once to its predecessor which is already sorted. The worst-case and average occur when the data is reversed so that each element must be moved to the beginning. The advantage is that the algorithm is in place with a constant memory.

Key points

Best case when the data is sorted
Worst case and average
Very efficient for small or nearly sequential data
Space complexity O(1), in-place

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.