Insertion Sort

Insertion sort is a simple sort algorithm
that works similar to the way playing cards sort.

Let’s say we have an array that is virtually split
into sorted and unsorted parts.
The values from the unsorted part are taken
and put into the correct position in the sorted part.

The algorithm looks like this:

To sort an array of size n in ascending order, we perform the following steps:

step 1

We iterate over the array starting from the second element up to the last element of the array.

step 2

Compare the current item with its predecessor.

step 3

If the current item is smaller than its predecessor,
we compare it with the previous items if any.
Then we move the larger elements up one position
to make space for the replaced element.

Let’s see it on an example:

We have a 5 element array [42, 41, 43, 25, 26 ]
we want to sort in ascending order.

step 1 – We iterate over the array starting from the second element to the last element of the array. As you probably know The second element of the array has the index 1.
step 2 – Compare the current element with its predecessor.
step 3 – If the current item is smaller than its predecessor,
we compare it with the previous items if any.
Then we move the larger elements up one position
to make room for the replaced element.

Since 41 is less than 42, we shift 42 and insert 41 before 42
41, 42, 43, 25, 26

We do the next iteration of the loop
43 will stay in place because all the elements preceding it are less than 43
41, 42, 43, 25, 26

We do the next iteration of the loop
25 will move to the beginning, and all other items 41 through 43 will move one position forward from their current position.
25, 41, 42, 43, 26

We do the next iteration of the loop
26 will move to position over 25, and elements 41 to 43 will move one position forward in relation to their current position.
25, 26, 41, 42, 43

We get a sorted array in ascending order.

Implementation in C# code

public class InsertionSort
{
        public static void Main(string[] args)
        {
            int[] arrayToSort = { 42, 41, 43, 25, 26 };
            SortArray(arrayToSort);
            PrintArray(arrayToSort);
        }

        private static void SortArray(int[] data) 
        {
            for (int i = 1; i < data.Length; ++i)
            {
                int current = data[i];
                int j = i - 1;
  
                while (j >= 0 && data[j] > current)
                {
                    data[j + 1] = data[j];
                    j = j - 1;
                }

                data[j + 1] = current;
            }
        }

        private static void PrintArray(int[] data)
        {
	    Console.Write("Sorted array:\n");

            for (int i = 0; i < data.Length; ++i)
                Console.Write(data[i] + " ");

            Console.Write("\n");
        }
}

Output:

25 26 41 42 43

Insertion sort takes maximum time
if items are sorted in reverse order.
And it takes minimum time when items are already sorted.

When can we use

Insertion sort is used when the number of elements is small.
It can also be useful when the input array is almost sorted,
only a few elements are misplaced in a full large array.