# How to create an algorithm when given the invariant

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

• How do you understand the concept of “invariant”? An invariant is a property that is supposed to hold for some thing. – Guildenstern Nov 7 '17 at 13:08
• Yes, this is why I don't understand how I'm supposed to create an algorithm where something like that holds true at all times.. – chala Nov 7 '17 at 13:10
• Don’t you understand the concepts of invariants in general, or this invariant in particular? I’ll invite you to ask about it in chat so that you can hash this out. ☺ – Guildenstern Nov 7 '17 at 13:12
• At every step of your algorithm, the invariant should hold. I think you can use selection sort starting from the end. – klaus Nov 7 '17 at 16:56

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$?