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.
My favorite sorts are random sort (toss them up, see where they fall. are they sorted?) and bead sort (connect 4 sort).
One is potentially O(1) sort and the other is potentially O(n). haha. But in practice they are terrible. Love it.
This sort is neat too.