Internet reactions to that sorting algorithm

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.

Most popular coverage

• Hacker News: probably the place that first broke the news. You will find all kinds of discussions ranging from someone immediately mistaking it as exchange sort and claiming that it (exchange sort) is their invention; to someone claiming they used it as the first sorting algorithm to introduce sorting to students (yeah sure...); to someone saying the algorithm has a "perverse beauty"; to someone repeatedly arguing the paper should have been a blog post instead; etc.


• 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

  — Lynn (@chordbug) May 7, 2022



• And we have at least one person with proven expertise who liked the algorithm: this tweet describes it as "beautiful" and that "What I find beautiful here is that such a combination of short, concise, counter-intuitive and **correct** exists."

  Beautiful. https://t.co/bPRnqhCpLS pic.twitter.com/oOpte7UnAF

  — Petar Veličković (@PetarV_93) October 6, 2021

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.

  Someone else told me privately that they proved its correctness in Coq, 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.

Used in teaching

• It appeared as an exercise in an algorithms course in Bristol;
• 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.

Some more examples of...

Those who understood it first time round...

Those who took a while...

And those who didn't.