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.

  • bandwidthcrisis@lemmy.world
    12·
    11 days ago

    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.

    • 14th_cylon@lemmy.zip
      3·
      11 days ago

      it would sort odd and even lists in opposite orders

      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 swap is reversed.