The first element in the array is assumed to be sorted. Take the second element and store it separately in key
.
key
with the first element. If the first element is greater thankey
, then key is placed in front of the first elemet.Now, the first two elements are sorted.
In a similar way, place every unsorted element at its correct position.
Pseudocode
Code