Insertion Sort
- Ω( n )
- Θ( n2 )
- O( n2 )
- space O( 1 )
- Comparisons count only element-against-element checks; loop and index checks are never counted.
- Reads and writes include reads and writes to helper buffers (merge, counting, radix, bucket and tim sort).
- A swap counts once, as a swap. It is never also counted as a read or a write.
- Real time is the average time of the counted sort on this device over repeated runs, measured once before playback and independent of animation speed. Visual time is the time spent animating, excluding pauses.
How insertion sort works
Insertion sort is a simple sorting algorithm that organizes elements in an array by repeatedly shifting elements to the right until the correct position for the current element is found. For each element, it compares it with the elements in the sorted sublist and shifts elements that are greater than the current element to the right until the correct position for the current element is found.
Read more
Insertion sort has a time complexity of O(n²) on average, but it has a better performance on small data sets and on lists that are already partially sorted. Because of this characteristic, insertion sort is often used as a simple sorting algorithm in embedded systems and other resource-constrained environments. It's also a good choice for educational purposes and simple cases.
| Best time | Ω( n ) | good |
|---|---|---|
| Average time | Θ( n2 ) | poor |
| Worst time | O( n2 ) | poor |
| Worst space | O( 1 ) | good |
Big O notation gives the lower, average and upper bounds of an algorithm. Time complexity bounds the number of operations; space complexity bounds the extra memory it uses.