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 :
- It is efficient for smaller data sets.
- 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)