I learned about this from Matt Parker’s Stand-Up Maths channel. It was originally conceived as a counterexample, a sorting algorithm that was obviously broken, but it does actually sort correctly. The algorithm:
for i = 1 to n do
for j = 1 to n do
if A[i] < A[j] then
swap A[i] and A[j]
It has a few quirks (like j accessing elements outside of i’s range, and the A[i] < A[j] comparator being backward) that should break it, but they all work together to make the algorithm correctly (if inefficiently) sort the input.
paper describing the algorithm in more detail.
That is just a bubble sort, except the comparisons are done in different order than conventional bubble sort…
Indeed it is, Matt mentions in the video that it was originally conceived as a counterexample for students first learning about sorting algorithms, and I think in that instance it makes sense to take bubble sort and try to mangle it so the students have at least some frame of reference while debugging it. It just so happens that the mangling produced a different, weird but still valid kind of bubble sort, which I find charming.
It really does look more broken the more I look. I began to think that it would sort odd and even lists in opposite orders, since half the time it’s comparing pairs the opposite way around.
not sure why you see different behaviour based on parity, but it does sort in descending order. that is why the inequality operator in
if A[i] < A[j] then swapis reversed.