How to create an algorithm when given the invariant
Observations:


For $i=0$, you don't know anything about the array.
For $i=n$, the array is sorted.


So the idea is to go from $i=0$ to $n$ while maintaining the invariant. This is similar to an inductive proof; in fact, you'll get an inductive algorithm.


Start with the input array and $i=0$; clearly, the invariant is maintained.
For some $i \geq 0$, assume that the invariant holds. What do you do to ensure the invariant holds for $i+1$?


I'll let you take it from here.