Insertion Sorting:
It is a simple Sorting algorithm which sorts the array by shifting elements one by one. Following are some of the important characteristics of Insertion Sort.
It has one of the simplest implementation
It is efficient for smaller data sets, but very inefficient for larger lists.
Insertion Sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency.
It is better than Selection Sort and Bubble Sort algorithms.
Its space complexity is less, like Bubble Sorting; inerstion sort also requires a single additional memory space.
It is Stable, as it does not change the relative order of elements with equal keys.
How it works
Sorting using Insertion Sort Algorithm
int a[6] = {5, 1, 6, 2, 4, 3};
int i, j, k; for(i=1; i<6; i++)
{
k = a[i]; j = i-1;
while(j>=0 && k < a[j])
{
a[j+1] = a[j];
j--;
}
a[j+1] = k;
}
Complexity Analysis of Insertion Sort
Worst Case Time Complexity : O(n2)
Best Case Time Complexity : O(n)
Average Time Complexity : O(n2)
Space Complexity : O(1)