Best Code For Insertion Sort in Programming

Insertion Sort Algorithm

In the Insertion Sort, the array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list. This algorithm is not suitable for large data.

Insertion Sort Working Algorithm Example  

Algorithm

Step 1 − If it is the first element, it is already sorted. Return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the
 Value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Insertion Sorting Code Using C# Language

Complexity Analysis of Insertion Sorting

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