Insertion Sort

Insertion sort is a very simple sorting algorithm which the sorted array is built one element at a time.
The main advantage of insertion sort is that it can efficiently be implemented on data set that are already substantially sorted .
For insertion sort the best case occurs when the array is already sorted ; while the worst case happens when the array is sorted in the reverse order.
Best case :O(n)
Worst case :O(n^2)

Technique:

1. We first divide the array to be sorted into two sets.One that stores the sorted value while the other stores unsorted values.
2. The sorting algorithm proceeds until there are elements in the unsorted set.
3. Initially we take the first element of the array (index 0)to be in the sorted set while the rest of the elements are in the unsorted set.
4. During each iteration of the algorithm, the first element in the unsorted set is picked up and inserted into the correct position of the sorted set. 

Source code :




Output:

Complexity:

The number of comparisons of elements in the worst case is

  (N-1) + (N-2) + ... + 1
= (N-1)*N/2

i.e. O(N²).

The average case time-complexity is O((N-1)*N/4), i.e. O(N²).
The best-case time complexity is when the array is already sorted, and is O(N).