[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!)