What is Insertion Sort?

Insertion sort is a sorting algorithm that sorts a collection of elements by inserting each element into its correct position in the sorted collection.

How to implement Insertion Sort?

To implement insertion sort, we need to insert each element into its correct position in the sorted collection.

Example

Let's sort the collection [3, 2, 4, 1, 2, 1] using insertion sort.

First, we need to insert each element into its correct position in the sorted collection.

Element	Sorted Collection
3	3
2	2, 3
4	2, 3, 4
1	1, 2, 3, 4
2	1, 2, 2, 3, 4
1	1, 1, 2, 2, 3, 4

The sorted collection is [1, 1, 2, 2, 3, 4].