Python DSALesson 107Free preview

Insertion Sort

This lesson is part of Python · All levels

Summary

This lesson discusses Insertion Sort, an algorithm that sorts data by placing one element in the correct position among the elements that have already been sorted. It works the same way as when we're putting together cards in our hands. Insertion sort is very efficient for small data or data that is almost sorted because it reaches O(n) in its best case.

Key points

The elements are taken from the right side and then moved to the left until they find their position.
The left side of the list is always in a sorted state while the algorithm is running.
The best complexity for the data is already sorted and the worst for the reverse data.
The insertion sort is stable and in-place, so it doesn't need any significant extra memory.
It's practically used as a sequencing subroutine on small data bits on advanced algorithms.

Full lesson

Code examples and quizzes

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