Is this the simplest (and most surprising) sorting algorithm?
Any measurement of &quot;code complexity&quot; is relative to some particular computational basis; which one do we choose?<p>In APL sorting the array P in ascending order is just<p><pre><code>    P[⍋P]
</code></pre>
which result you can optionally assign back to P by prepending &quot;P←&quot;.  So, by the APL measure, none of these algorithms is &quot;as simple as&quot; invoking the builtin sort operator.  (Which is probably also faster.)  APL doesn&#x27;t actually have any &#x27;syntax that&#x27;s basically &quot;for i = x to y&quot;.&#x27;<p>If we take Perl golf as our measure of &quot;code complexity&quot; you can&#x27;t use a for-loop for dumbsort, because zeroing the ostensible loop counter doesn&#x27;t reset the loop; there&#x27;s a hidden loop counter you can&#x27;t alter.  You have to use an explicit while loop, which makes the cantbelievesort much simpler.  Smalltalk and Python are the same way.  But of course the shortest way to sort in all three languages is to invoke the built-in sort function: sort @p, p asSortedCollection, p.sort().<p>(You&#x27;re right about FORTRAN and BASIC, though.  You can futz with loop counters in those languages, just like in C.)<p>That&#x27;s why I chose C and machine code as my metric.  Smalltalk and Python maintain this hidden loop counter in the implementation, and also do garbage collection behind the scenes (which you might think was irrelevant, but the write barrier can significantly slow down heavily mutating algorithms like this one) and bounds checking.  Numpy and APL additionally do implicit array broadcasting.  All of these languages (except FORTRAN and BASIC) have built-in sort routines that are simpler to invoke than writing your own sort function.  So I was looking for the language that would keep me as honest as possible.<p>But of course in a different machine language the answer might be different.  For example, I haven&#x27;t seen an instruction set with dedicated looping instructions that support nested loops, but make it inconvenient to clobber the loop counter in the middle of the loop, but it would be easy to design one, and there might be some advantage to doing so.  (Code density, maybe, or unrolling iterations of the loop into a pipeline.)  Then dumbsort would lose, because as in Python, it would have to be written as a regular while loop, which usually costs four instructions: an increment, a compare, a conditional jump, and an unconditional jump.<p>I think the i-=2 tweak you suggest converts dumbsort into gnomesort, which is just a sort of pessimized insertion sort.  As your &quot;saturating&quot; comment suggests, gnomesort needs an additional operation to avoid running off the beginning of the array; some instruction sets do provide saturating arithmetic (it&#x27;s often useful for DSP and graphics, even if it&#x27;s not as often useful for indexing arrays), and many others provide a binary &quot;max&quot; operation (SSE&#x27;s PMAXSW and friends, as well as, say, APL ⌈) which could convert an ordinary subtraction into a saturating subtraction.