Is this the simplest (and most surprising) sorting algorithm?
For me, this is a lesson in the power of semantics. If one re-writes the if statement and switches the order,<p><pre><code>   if A[j] > A[i] then
</code></pre>
I find the correctness of the algorithm to be significantly more obvious.<p>It is true that i >= j, and sorted ascending values will have the property A[i] >= A[j].<p>It follows that swapping happens when the values are <i>out of order</i>, when<p><pre><code>   A[j] > A[i]</code></pre>