Insertion sort is a very simple, stable, in-place sorting algorithm. It performs well on small sequences but it is much less efficient on large lists. At every step, the algorithms considers the i-th element of the given sequence, moving it to the left until it is in the correct position.
for j = 1 to length(A) n = A[j] i = j - 1 while j > 0 and A[i] > n A[i + 1] = A[i] i = i - 1 A[i + 1] = n
Consider the following list of integers:
[5, 2, 4, 6, 1, 3]
The algorithm will perform the following steps: