[OJFord]

Why is this algorithm at all surprising?

(I'm really not trying to brag - I assume I must be missing something, that I'm naïve to think it obviously works, and it actually works for a different reason.)

In plain English - 'for every element, compare to every element, and swap position if necessary' - .. of course that works? It's as brute force as you can get?

[Asooka]

The comparison is not the way you'd expect. Index j goes past index i, but the comparison doesn't change. What you propose is a condition more like

    if ((a[i] < a[j]) != (i < j)) swap(a, i, j) ;

Which obviously works.

The surprising algorithm sorts even though it swaps elements that are already ordered.

[OJFord]

Ok, I think I see why it's a bit weird '1,2,3 when i=1 and j=3 it swaps them anyway' sort of thing?

But i-loop comes through 'afterwards', so when i=3 (value now 1) and j=1 (3) it sets them straight.

It still seems quite intuitive, but I think I cheated by skimming over it initially and thinking it was clear, whereas actually I've thought about it more now.

(Not to compare myself to anything like him, I'm no mathematician at all, but I'm reminded of an amusing Erdós anecdote in which he apparently paused mid-sentence in some lecture, left the room, and came back some time later continuing 'is clearly [...]' or similar!)

[YetAnotherNick]

If the second loop is from j = i to n, it is easy to see that it will sort in decreasing order. But notice j = 1 to n, then suddenly it will sort in increasing order

[shp0ngle]

look again at the comparison direction.

It is opposite!

It works but not as you think it does.