Well, people talked about the algorithm... though maybe not in the way I
was expecting. Here I will first show you a few places where it is talked
about most (and therefore contain many responses from those who understood
it, but also a lot more from those who didn't). Then in the next few sections
I will highlight a few from those who (1) understood what it is
outright and liked it, (2) took them a while, and (3) didn't see what it
is and said something frankly quite stupid.
This youtube video gives a nice animation (better than most of the other
animations out there that are either not very clear or even showing the
wrong algorithm like exchange sort), and also an explanation on it being
a combination of insertion sort and selection sort, similar to
what I wrote here. It also describes the
algorithm as "simplest (for a sufficiently perverse definition of the word
simple)". I'll take that as a compliment.
Among tweets about the algorithm, this is probably the one with the most
reactions. The OP did not say what they think about it at all, but you
can check the numerous (good and bad) responses. Perhaps not too
surprisingly, I find that generally replies are more likely to be from people
who dismissed it without knowing what it really is, and quoted tweets are
more likely to come from those who understood and liked it.
âIs this the simplest (and most surprising) sorting algorithm ever?â
https://t.co/ucjbOCh0mA
Abstract:
We present an extremely simple sorting algorithm. It may look
like it is obviously wrong, but we prove that it is in fact correct.
pic.twitter.com/sYZpagPLAo
For those who still haven't understood and still mocking the algorithm,
you may want to see what others say...
This computer scientist describes it as "beautiful"
and that "What I find beautiful here is that such a combination of short,
concise, counter-intuitive and **correct** exists."
This one gives a perfect description: a "programming optical illusion".
I love this stoopid thing. The surprise on seeing that less than sign totally plays on our assumption about how you would sensibly write those nested loops. Itâs like a programming optical illusion.
If you are still fully confident that you got it right and everyone else is dumb,
see more examples of what others said:
Academic communities
The algorithm seems to be of interest to the formal verification /
automated theorem proving community. In addition to fooling humans, the
algorithm also seems to trip up many simple theorem proving attempts.
For example the following blog post talks about their (difficult)
experience of proving it with SPARK:
I can't believe that I can prove that it can sort
(Thanks, at last someone play along with the name of the algorithm!)
They are also one of the many people who claimed they discovered the same
algorithm back in their school days... well we only have their word
for that.
And someone
proved its correctness in Coq.
I was told privately this was
used it as a project in a formal verification course at Google, and that
"it's proving to be an excellent étude for proof by induction".
Some
Taiwan facebook groups about algorithms
reported it, and compared it to the
"Floyd-Warshall wrong loop order doesn't matter if you repeat it 3 times"
paper.
It seems to have appeared as an exercise
in a University of Toronto course
(but yes, that link goes to those notorious cheating sites). And they called
it NoWaySort.
