insertion sort

Insertion sort is a simple sorting algorithm that builds a sorted sequence one element at a time, taking each new value and slotting it into its correct place among the values already sorted.

It mirrors the way many people arrange a hand of playing cards. The algorithm keeps a sorted section at the front of the collection, then repeatedly takes the next unsorted element and shifts the larger sorted values one position right until a gap opens for it. Because it only rearranges elements within the original collection, it sorts in place with a constant amount of extra memory.

Step through a full sort below to watch that sorted section grow, one insertion at a time.

Interactive diagram — enable JavaScript to view.

Insertion sort has several properties that set it apart from other quadratic sorts:

  • Stable: It preserves the original order of elements that compare equal.
  • Adaptive: It runs faster on input that is already nearly sorted, approaching O(n) in the best case.
  • Online: It can sort a sequence as the elements arrive, without needing the whole input up front.

Its running time is where the trade-offs show. On data that is already sorted, it makes a single pass in linear time, O(n). On random or reverse-sorted input, both the average and worst cases degrade to quadratic time complexity, O(n^2), because each insertion may scan and shift the entire sorted section.

That quadratic cost makes insertion sort impractical for large collections, but its low overhead still beats asymptotically faster algorithms on small ones. For that reason, hybrid sorts such as Timsort, the algorithm behind Python’s sorted() and list.sort(), fall back to insertion sort for short runs.

Sorting Algorithms in Python

Tutorial

Sorting Algorithms in Python

In this tutorial, you'll learn all about five different sorting algorithms in Python from both a theoretical and a practical standpoint. You'll also learn several related and important concepts, including Big O notation and recursion.

intermediate algorithms python

For additional information on related topics, take a look at the following resources:

By Martin Breuss • Updated Aug. 10, 2026
Computer Science Glossary Share Feedback