insertion sort all time complexities code example

Example: what is time complexity of insertion sort

Time Complexity is: 
If the inversion count is O(n), 
then the time complexity of insertion sort is O(n).

Some Facts about insertion sort:
1. Simple implementation: Jon Bentley shows a three-line C version, and a five-line optimized version[1]
2. Efficient for (quite) small data sets, much like other quadratic sorting algorithms
3. More efficient in practice than most other simple quadratic (i.e., O(n2)) 
algorithms such as selection sort or bubble sort
4. Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn)
when each element in the input is no more than k places away from its sorted position
5. Stable; i.e., does not change the relative order of elements with equal keys
6. 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