Insertion Sort with Example and Time Complexity

Sorting is process of arranging the elements in particular order by using any property. Here property means one can sort in ascending order or descending order or the nature of numbers.

Insertion sorting is one of the most common sorting technique used by card players. As they pickup each card they insert it into the proper sequence in their hand. The concept extend well into computer sorting. In each pass of an insertion sort, one or more pieces of data are inserted into their correct location in an ordered list.The main idea behind insertion sort is that is that it inserts each item into its proper place in the final list.

Insertion Sort Example

The insertion sort algorithm is performed using following steps...

Step 1 - Assume that first element in the list is in sorted portion of the list and remaining all elements are in unsorted portion.

Step 2: Consider first element from the unsorted list and insert that element into the sorted list in order specified.

Step 3: Repeat the above process until all the elements from the unsorted list are moved into the sorted list.

Complexity of the Insertion Sort Algorithm

To sort a unsorted list with 'n' number of elements we need to make (1+2+3+......+n-1) = (n (n-1))/2 number of comparisons in the worst case. If the list already sorted, then it requires 'n' number of comparisons.

Worst Case : O(n²)
Best Case : Ω(n)
Average Case : Θ(n²)

1. C Program for insertion sort check here
2. Java program for insertion sort check here