[ssquared361]

I'm looking for help with a proof of the correctness of flash sort. Is anyone familiar with flash sort? I am trying to determine a useful loop invariant, but I am getting nowhere. I first thought that I could use A[1...j] are in their correct bins, but this is only true after the loop iteration, not before (Beginning with j = 1 and progressing toward length(A)... at the very first iteration, it is not true that A[1...1], or A[1], is in its correct bin, A[j] is the element to be moved.) I really need help with this.

For anyone interested in helping, but unfamiliar with flash sort:
http://drdobbs.com/a...esign/184410496
http://www.neubert.n...es.html#Sprung3