Insertion Sorting

It is a simple Sorting algorithim which sorts the array by shifting elements one by one.

Following are some of the important characteristics of Insertion Sort : 

1. It is efficient for smaller data sets.
2. It's Space Complexity is less, like Bubble Sorting, insertion sort also requires a single additional memory space.

Working of Insertion Sort - 

Note : Image source via Internet 

Complexity Analysis : 

Worst Case Time Complexity : O(n2)
Best Case Time Complexity : O(n)
Average Time Complexity : O(n2)
Space Complexity : O(1)