Data Structures and Algorithms - Insertion Sort

Hello Guyz,
Now I'm Going to show you How Insertion Sort works.Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quick sort, heap sort, or merge sort. However, insertion sort provides several advantages:

• Simple implementation: Bentley shows a three-line C version, and a five-line optimized version.
• Efficient for (quite) small data sets
• More efficient in practice than most other simple quadratic (i.e., O(n²)) algorithms such as selection sort or bubble sort
• Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(nk) when each element in the input is no more than k places away from its sorted position
• Stable; i.e., does not change the relative order of elements with equal keys
• In-place; i.e., only requires a constant amount O(1) of additional memory space
• Online; i.e., can sort a list as it receives it

When people manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort

Insertion Sort is Work like this :

Code is :

-Vishva Rodrigo-