Paper about this with proof of how/why it works: https://arxiv.org/pdf/2110.01111, which says:
“There is nothing good about this algorithm. It is slow – the algorithm obviously runs in Θ(n2) time, whether worst-case, average-case or best-case. It unnecessarily compares all pairs of positions, twice (but see Section 3). There seems to be no intuition behind it, and its correctness is not entirely obvious. You certainly do not want to use it as a first example to introduce students to sorting algorithms. It is not stable, does not work well for external sorting, cannot sort inputs arriving online, and does not benefit from partially sorted inputs. Its only appeal may be its simplicity, in terms of lines of code and the “symmetry” of the two loops.”*
I'd like to see a formal proof of this.
Not because I don't believe it's true, but because this might be a nice entry into formal proofs.
Why would it not sort? It looks like the method that most people use to sort things manually.
I can't believe some people can read grey text on slightly lighter grey background
It is very efficient, just for arrays not larger than 2 elements :)
Previously (2021): https://news.ycombinator.com/item?id=28758106
I'm pretty impressed by both Grok's and Gemini's static analysis of it. (I changed the name of the function to algo and asked them to figure out if it's supposed to be a sort algorithm or a search algorithm. Both got it right.)[1] If someone else could please check the same prompt on ChatGPT and Claude (which I don't have) please link.
[1]
https://grok.com/share/c2hhcmQtMw_77a3a16f-642c-4ea7-95c7-28...
and
The reason it works is because you get redundancy with everything referencing everything else. It looks like one of those CPU core to core latency diagrams. Without iterating like this the sort could only flow in one direction. If we modified the conditional to handle both cases you could split the square along the identity diagonal and only use half.