Learn Computer Science
Developing a more interesting World
"Computer science is no more about computers than astronomy is about telescopes."
Edsger Dijkstra
Free beginner - intermediate level computer science tutorials
Insertion Sort
Tutoring > Data Structures > Insertion Sort
Insertion sort is used for sorting an array and has a time complexity of O(n^2) in the worst and average cases. It does have a best case time complexity of O(n) but that is only if the array is already sorted.
x is inserted into it's correct position in the left part:
How it works
​Insertion sort works by moving along the array one element at a time and checking the elements value against the ones to the left of the "boundary".
As an element is reached, the algorithm checks whether it is bigger or smaller than the elements in the sorted side (the left side) of the array.
The left dotted line in the diagrams to the left represent the boundary. Everything to the left of this is sorted, everything to the right is yet to be sorted.
An example
We will start with an unsorted array : {7, 3, 2, 8, 1, 6}
|7 3 2 8 1 6
7 | 3 2 8 1 6 <- This first iteration can be ommited.
3 7 | 2 8 1 6 <- The 3 is smaller than the 7 so goes before it.
2 3 7 | 8 1 6 <- The 2 is smaller than the 3 so goes before it.
2 3 7 8 | 1 6 <- The 8 is larger than the 7 so stays put.
1 2 3 7 8 | 6 <- The 1 is smaller than all sorted elements so goes first.
1 2 3 6 7 8| <- Finally the 6 is also put into it's correct position.
The boundary starts at the left and goes through one element at a time.
Each element is checked against the sorted part (to the right of the boundary) and inserted into it's correct location. After the boundary has reached the end and the last element has been inserted, the array is fully sorted.