Introduction to Algorithm 2.1

The book says that the insertion sort is a”n efficient algorithm for sorting a small number of elements”.

# EN

## Algorithm

The idea of insertion sort is also easy, given a list of numbers, simply loop through whole list, if the current value is larger than the left ones, move the current value to the index of the correct position, then move to the next value.

I found the example from Wikipedia:

The original list is [6, 5, 3, 1, 8, 7, 2, 4]. With the 1st value 6, there is no smaller value on its left, so the first round remains the same.

With the 2nd value 5, it’s obvious that 5 is smaller than 6, so move 5 to the left hand of 6, and then the list becomes [5, 6, 3, 1, 8, 7, 2, 4].

With the 3rd value 3, it’s smaller than both 5 and 6, so move 3 to the left hand of 5, and then the list becomes [3, 5, 6, 1, 8, 7, 2, 4].

Repeat same step for the rest values in list, eventually the list is sorted: [1, 2, 3, 4, 5, 6, 7, 8].

## Complexity

### Time Complexity

In the best case, time complexity is O(n), so it’s a good thing. However, in the worst case, as [8, 7, 6, 5, 4, 3, 2, 1], there is (n - 1) values in total require to be moved, and each value need to be move n times, so the number of inversion is: $\frac{(n*(n-1))}{2}$, which yields an O($n^2$) time complexity.

On the other hand, in the best case scenario, the time complexity is O($n$) since all the elements in the list needs to be iterated.

### Space Complexity

The space complexity is O($n$) since the algorithm only require 1 extra space to store current value.

## Pseudocode

From the book, on page 18: