insertion

<- Go Back

Insertion sort

This algorithm sorts the array of elements one item at a time. It is not efficient for a large list of elements.

Advantages:

• Simple to implement
• More efficient for small list of elements and partially sorted lists
• Efficient for the use of memory, it only requires O(1) of additional memory space

Procedure

1. Loop over positions in the array, starting with index = 1 (not 0 when the array is zero-based). That index contains the pivot.
2. Start temporal index (j) to index-1
3. While j >= 0 Do

• Compare pivot vs content at j
• if it is greater, move content of j to the right (and hold the pivot)
• Decrease j in 1

4. Set pivot content at j+1 (once j has reached the beginning of the array or the right place in the sorted elements at left side)

The pivot is the content at any new position hold separately, and you need to insert it into the correct place at the sorted sub-array to the left of that position.

The algorithm could start from the right or from the left (which is more common). The process is similar but opposite in the comparison and the direction of the movement of elements.

Time Complexity:

• Best O(n) (when it is already sorted)
• Average O(n^2)
• Worst O(n^2)

Tools of Reference

• Test at TestInsertionSort.py
• Video explanation (spanish)