Is this the simplest (and most surprising) sorting algorithm?
[Edit: I took a quick glance at the paper and got carried away; the rest of this comment is about a different algorithm apparently known as &quot;exchange sort&quot;, and an interesting property of it. The algorithm in the paper is actually different, and indeed more surprising.]<p>Hey! That&#x27;s <i>my</i> sorting algorithm! (Well, I&#x27;m sure it has been independently discovered many times, but one of those times was by me before I had learned of O(n log n) sorting; I used it many times including in the INOI 2004 programming contest, about which I asked the following question ten years ago in 2011 on math.SE about this algorithm and Catalan numbers, a truly surprising property that is not mentioned in this paper: <a href="https:&#x2F;&#x2F;math.stackexchange.com&#x2F;questions&#x2F;36022&#x2F;how-do-the-catalan-numbers-turn-up-here" rel="nofollow">https:&#x2F;&#x2F;math.stackexchange.com&#x2F;questions&#x2F;36022&#x2F;how-do-the-ca...</a><p>&gt; For situations where a quadratic-time sorting algorithm is fast enough, I usually use the following:<p><pre><code>    &#x2F;&#x2F;Given array a[1], ... a[n]
    for i = 1 to n:
        for j = i+1 to n:
            if a[i] &gt; a[j]:
                swap(a[i],a[j])
</code></pre>
&gt; It looks like bubble sort, but is closer to selection sort. It is easy to see why it works: in each iteration of the outer loop, `a[i]` is set to be the smallest element of `a[i…n]`.<p>----<p>Also: A few years ago I emailed Prof. Richard Stanley of <i>Enumerative Combinatorics</i> fame asking whether it was related to any of the hundreds of problems in his <i>Catalan Numbers</i> list, and he said he didn&#x27;t know a direct connection at the time (so maybe it&#x27;s an addition to his list?):<p>&gt; &gt; permutations equal to the product of all their inversions (in lexicographic order) [multiplying on the left]<p>&gt; Example: The permutation 1423 has two inversions (24) and (34), and the product (34)(24) is the same as 1423.<p>&gt; Non-example: The permutation 3412 has four inversions (13), (14), (23) and (24), and the product (24)(23)(14)(13) is 4321 which is not the same as 3412.<p>&gt; Among the permutations of {1, 2, 3, 4}, there are 14 examples (and 10 non-examples).<p>And 14 is C_4, the fourth Catalan number.