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

Programmer Humor

33288 readers
1004 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
[–] shape_warrior_t@programming.dev 3 points 2 weeks ago

As the addendum to the paper points out, this is more like insertion sort (with i and j in a confusing order) than bubble sort. The actual "important" part of the algorithm happens when j < i. (In fact, I'm quite certain there aren't even any swaps when j >= i after the first outer iteration.) (I think the page about people misremembering bubble sort is also worth looking at.)

Honestly, I think this might actually be "better" than bubble sort, in the sense that at least it's incredibly easy to remember and not that hard to get correct. The only place where you could realistically mess up is confusing the relative order of i and j -- and any amount of nontrivial testing will immediately show the error, since it reverses the sort order. I'd probably reach for this if I, for whatever insane reason, had to code up a sorting algorithm by hand for some task where O(n^2) sorting was acceptable performance-wise. "Sort a list of 10 items in a very primitive programming language"-type deal.

(Now that I say that, I'm kind of tempted to use it in some example program for my own in-development programming language, which currently doesn't have a builtin sort function...)