You are absolutely correct, I was gun ho and got punished with internet shame, bellow is the correct proof. but the point still stands. Solution is even simple

You are absolutely correct, I was gun ho and got punished with internet shame, bellow is the correct proof. but the point still stands. Solution is even simpler: Empty case after 1 iteration (I=1) the largest number is at position 1 Base case: after 2 iterations (I=2) the 2 first elements are ordered, and the largest number is at position 2 Assume N case: after N iterations the first N numbers are ordered (within the sub list, not for the entire array) and the largest number is at position N N+1 case (I=N+1): For Every J<N+1 and A[J]>= A[I] nothing will happen From the first J where J<N+1 and A[J] < A[I] (denote x) each cell will switch as A[J] < A[J+1] At J=N+1 the largest number will move from A[N] to A[I] For every J>N+1 Nothing will happen as the largest number is at A[I] Not part of the proof but to make it clear we get: - for J<x A[J]<A[I] - for J=x A[J]=A[I] - for J<x A[J]>=A[I] and the list is ordered for the first J elements