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.
Seems straightforward enough. For j values of 1 to i it will not do anything because the largest element in the array has already been moved to position i in some earlier iteration in the i loop. For j values greater than i it then proceeds to find the largest remaining element place in position i.
For the
j > icase I think you’re right, it sorts largest to smallest (or, backwards), but for thej < icase it grabs larger values from[0, i]that it initially moved to the top of the array and slots them back in, effectively (if roundabout-ly) correcting the backwards sorting of thej > ipart of the algorithm. Sort of a “two wrongs that accidentally make a right” maneuver.