What is the use of insertion sort in data structure?

Question

Any practical example would be helpful?

Answer 1

It is a simple sorting algorithm which sorts the array by shifting element one by one.Following are some of the important characteristics of insertion sort.

1-It has one of the simplest implementation.
2-It is efficient for smaller data sets, but very inefficient for larger lists.
3-insertion sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency.
4-It is better than selection sort and bubble sort algorithms.
5-Its space complexity is less, like bubble sorting, insertion sort also requires a single additional memory space.
6-It is stable, as it does not change the relative order of elements with equal keys.

Sorting using Insertion Sort Algorithm:

int a [ 6 ] = { 5 , 1 , 6 , 2 , 4 , 3 } ;
int  i , j ,  key ;
for ( i=1; i < 6 ;   i + + )
  {
       Key= a [ i ];
       j = i - 1;
while ( j > = 0  &&  key  < a [ j ] )
      {
           a [ j + 1 ] = a [ j ] ;
            j - - ;
      }
          a [ j + 1 ] = key ;
   }