Insertion sort is one of the sorting technique used to sort a data structure like an array.

The general idea of the insertion sort is to partition the array into two parts

  • Sorted Partition
  • Unsorted Partition.

As the sorting progress, the sorted partition grows and the unsorted portion shrinks. And finally, we get a sorted array.

Insertion Sort Algorithm

At the start. The array is unsorted.

So we assume the first element (array[0]) to be sorted. And the rest of the elements are unsorted. Now we compare the first element (array[0]) with the second element (array[1]) of the array. And arrange them accordingly.

Now we have the first two elements sorted. Again we repeat the process with the third element of the array.

By doing this sorted partition grows and the array gets finally sorted.

C

Java

Output

Insertion Sort Overview

  • In-place algorithm (No need of extra arrays).
  • O(n²) time complexity – quadratic.
  • Stable algorithm (Doesn’t interchange same values in the array).

Leave a Reply

Close Menu