Insertion Sort

Average time complexity - O(n^2)

Best-Case time complexity - O(n)

Worst-Case time complexity - O(n^2)

Worst-case space complexity - O(1)

Insertion Sort is a simple but decently efficient iterative sorting algorithm. It works by find any element out of place, then swapping it with its neighbors until it is in place, starting on the second element (not the first because the first is already in place). It basically finds the smallest value and then moves it to the left until it is in place. It "inserts" the elements into their correct spots.

Let's say you have the following array:

4, 1, 5, 2, 3

Insertion Sort starts at the second element, which it compares to the first. If they are out of order (which they are), it swaps them.

1, 4, 5, 2, 3

Then it moves on to the second and third elements, which are in order. Next it compares the third and fourth elements, which are out of order, so it swaps them.

1, 4, 2, 5, 3

Now it decrements the indices it is comparing. So now it compares the third and second elements, which are also out of order. So it swaps.

1, 2, 4 5, 3.

Now it compares the first and second elements, which are in order, so it increases the index by one and then continues comparing.

It compares the second and third, which are in order. It then compares the third and fourth, which are also in order. Then it compares the fourth and fifth elements, which are out of order, so it swaps them.

1, 2, 4, 3, 5

Then it again starts the insertion process, and keeps shifting 3 down until it is in place. It compares the third and fourth elements, which are out of order, so it swaps them.

1, 2, 3, 4, 5

It then compares the second and third elements, which are correct, so it leaves the insertion process, and goes back to comparing. However, the last thing it did was compare the last two elements, so it has run out of elements to compare, and it is finished.