How to create an algorithm when given the invariant

Question

I am given the following invariant:

Invariant The greatest $i$ keys of an Array are always in sorted order on the last $i$ indices of the Array.

I am supposed to create a sorting Algortihm using this invariant. But I seem to have understood the concept of an Invariant differently, because with the information I find online, I can't find an idea for starting this problem. Do I have to create an algorithm that sorts the first $n-1$ elements in the array? Thanks for your help

Answer 1

Observations:

1. For $i=0$, you don't know anything about the array.
2. 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.