[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 "exchange sort", and an interesting property of it. The algorithm in the paper is actually different, and indeed more surprising.]

Hey! That's my sorting algorithm! (Well, I'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: https://math.stackexchange.com/questions/36022/how-do-the-ca...

> For situations where a quadratic-time sorting algorithm is fast enough, I usually use the following:

    //Given array a[1], ... a[n]
    for i = 1 to n:
        for j = i+1 to n:
            if a[i] > a[j]:
                swap(a[i],a[j])

> 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]`.

----

Also: A few years ago I emailed Prof. Richard Stanley of Enumerative Combinatorics fame asking whether it was related to any of the hundreds of problems in his Catalan Numbers list, and he said he didn't know a direct connection at the time (so maybe it's an addition to his list?):

> > permutations equal to the product of all their inversions (in lexicographic order) [multiplying on the left]

> Example: The permutation 1423 has two inversions (24) and (34), and the product (34)(24) is the same as 1423.

> 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.

> Among the permutations of {1, 2, 3, 4}, there are 14 examples (and 10 non-examples).

And 14 is C_4, the fourth Catalan number.