this post was submitted on 01 Sep 2026
92 points (100.0% liked)

Programmer Humor

33298 readers
1067 users here now

Welcome to Programmer Humor!

This is a place where you can post jokes, memes, humor, etc. related to programming!

For sharing awful code theres also Programming Horror.

Rules

founded 3 years ago
MODERATORS
anzo@programming.dev
Feyter@programming.dev
BurningTurtle@programming.dev
pylapp@programming.dev
92
ICantBelieveItCanSort Sort (piefed.blahaj.zone)
submitted 2 weeks ago by queerlilhayseed@piefed.blahaj.zone to c/programmer_humor@programming.dev
10 comments fedilink hide all child comments
 

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.

you are viewing a single comment's thread
view the rest of the comments
[–] 14th_cylon@lemmy.zip 48 points 2 weeks ago (1 children)

That is just a bubble sort, except the comparisons are done in different order than conventional bubble sort...

[–] queerlilhayseed@piefed.blahaj.zone 24 points 2 weeks ago (1 children)

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.

[–] bandwidthcrisis@lemmy.world 12 points 2 weeks ago (1 children)

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 points 2 weeks ago* (last edited 2 weeks 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.