Is this the simplest (and most surprising) sorting algorithm?
The algorithm from the paper is indeed an astonishingly simple sorting algorithm, and it is indeed surprising that it works:<p><pre><code>    void
    cantbelievesort(int *p, size_t n)
    {
      int tmp;
      for (size_t i = 0; i &lt; n; i++) {
        for (size_t j = 0; j &lt; n; j++) {
          if (p[i] &lt; p[j]) tmp = p[i], p[i] = p[j], p[j] = tmp;
        }
      }
    }
</code></pre>
That&#x27;s 10 lines of code according to David A. Wheeler&#x27;s &#x27;SLOCCount,&#x27; though arguably 9 would be fairer.  Its cyclomatic complexity is 3, with a deepest statement nesting level of 4, and it has 5 variables: three locals plus two arguments.  It compiles to these 17 amd64 instructions, occupying 44 bytes of code, although I could probably shave off a third of that if I wrote it by hand:<p><pre><code>      4007cc:       31 c0                   xor    �x,�x
      4007ce:       eb 22                   jmp    4007f2 &lt;cantbelievesort+0x26&gt;
      4007d0:       8b 0c 87                mov    (%rdi,%rax,4),�x
      4007d3:       44 8b 04 97             mov    (%rdi,%rdx,4),%r8d
      4007d7:       44 39 c1                cmp    %r8d,�x
      4007da:       7d 07                   jge    4007e3 &lt;cantbelievesort+0x17&gt;
      4007dc:       44 89 04 87             mov    %r8d,(%rdi,%rax,4)
      4007e0:       89 0c 97                mov    �x,(%rdi,%rdx,4)
      4007e3:       48 ff c2                inc    %rdx
      4007e6:       eb 02                   jmp    4007ea &lt;cantbelievesort+0x1e&gt;
      4007e8:       31 d2                   xor    �x,�x
      4007ea:       48 39 f2                cmp    %rsi,%rdx
      4007ed:       75 e1                   jne    4007d0 &lt;cantbelievesort+0x4&gt;
      4007ef:       48 ff c0                inc    %rax
      4007f2:       48 39 f0                cmp    %rsi,%rax
      4007f5:       75 f1                   jne    4007e8 &lt;cantbelievesort+0x1c&gt;
      4007f7:       c3                      retq   
</code></pre>
However, arguably, <i>this</i> sort routine is <i>even simpler</i>.  It may or may not be surprising that it works:<p><pre><code>    void
    dumbsort(int *p, size_t n)
    {
      int tmp;
      for (size_t i = 1; i &lt; n; i++) {
        if (p[i] &lt; p[i-1]) tmp = p[i], p[i] = p[i-1], p[i-1] = tmp, i = 0;
      }
    }
</code></pre>
By the same metric, that&#x27;s <i>only 8</i> lines of code (also only 8 by my &quot;fairer&quot; metric), its cyclomatic complexity is <i>only 2</i>, its deepest statement nesting level is <i>only 3</i>, and it has <i>only 4</i> variables (the same two arguments, but two locals instead of three).  It compiles to <i>only 15 amd64 instructions</i>, occupying <i>only 43</i> bytes:<p><pre><code>      4007f8:       b8 01 00 00 00          mov    $0x1,�x
      4007fd:       eb 1e                   jmp    40081d &lt;dumbsort+0x25&gt;
      4007ff:       4c 8d 04 87             lea    (%rdi,%rax,4),%r8
      400803:       48 8d 54 87 fc          lea    -0x4(%rdi,%rax,4),%rdx
      400808:       41 8b 08                mov    (%r8),�x
      40080b:       44 8b 0a                mov    (%rdx),%r9d
      40080e:       44 39 c9                cmp    %r9d,�x
      400811:       7d 07                   jge    40081a &lt;dumbsort+0x22&gt;
      400813:       45 89 08                mov    %r9d,(%r8)
      400816:       31 c0                   xor    �x,�x
      400818:       89 0a                   mov    �x,(%rdx)
      40081a:       48 ff c0                inc    %rax
      40081d:       48 39 f0                cmp    %rsi,%rax
      400820:       72 dd                   jb     4007ff &lt;dumbsort+0x7&gt;
      400822:       c3                      retq   
</code></pre>
On every complexity metric that was ready to hand, dumbsort is simpler than cantbelievesort.  Except computational complexity: dumbsort is O(N³) while cantbelievesort is only O(N²).<p>Dumbsort is similar to gnome sort, but arguably somewhat simpler: whenever it finds an out-of-order pair, after reversing it, it throws up its hands and starts over (i = 0, xor �x, �x).<p>I don&#x27;t think I invented it, but I can&#x27;t remember who did.  I&#x27;d be grateful for pointers.