##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Insert each element into its sorted position.
Insertion sort: Build sorted array by inserting each element into correct position.
Left portion sorted. Take next unsorted element. Shift larger elements right. Insert.
Example : sorted. Insert :
Insert :
Insert :
Insert :
Insert :
Time: worst, nearly sorted.
