[roenxi]

If it looks "obviously wrong" the quick proof that it works ... the j loop will move the largest unsorted element in the array into a sorted position. Since the i loop executes the j loop n times, the array must be sorted (since the n largest elements will be in the correct order).

EDIT

^W^W^W

Nope, I'm wrong. I did a worked example on paper. I think the devious thing here is the algorithm looks simple at a lazy glance.

To sort: 4-3-6-9-1, next round pivot for the i loop in [].

    [4]-3-6-9-1
    9-[3]-4-6-1
    3-9-[4]-6-1
    3-4-9-[6]-1
    3-4-6-9-[1]

    1-2-3-6-9 & sorted

I can see that it sorts everything to the left of a pivot, then because it does that n times it comes to a sorted list. A reasonable proof will be more complicated than I thought.

[blueflow]

This somewhat looks like bubble-sort minus the early exit.

[zajio1am]

It is just quirky insert-sort. In each outer cycle, it inserts value originally from the A[i] position to already sorted sequence A[1]..A[i-1], while using A[i] as a temporary variable to shift higher part of the sorted sequence one position up.

[MrYellowP]

It is BubbleSort. At least that's how I've learned it in the 80s.

[phkahler]

The list on the left (index less than i) is always sorted. The ith element is inserted by the j loop and the rest of the list is shifted right by one element by repeated swapping with the ith position. Nothing to the right changes because the ith element is the max of the entire list, which seems to be a red herring for analysis.