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

Programmer Humor

33288 readers
1018 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
[–] chamaeleon@fedia.io 5 points 2 weeks ago (1 children)

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.

Edit: I'm leaving my incorrect thought above as is for posterity. As pointed out when j is less than i it does of course swap again resulting in a more difficult (for me) visualization of what the end result looks like. Time to have some fun with it (could read about it, but programming is more fun and I like to experiment).

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

For the j > i case I think you're right, it sorts largest to smallest (or, backwards), but for the j < i case 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 the j > i part of the algorithm. Sort of a "two wrongs that accidentally make a right" maneuver.

[–] 14th_cylon@lemmy.zip 1 points 2 weeks ago* (last edited 2 weeks ago)

Sort of a “two wrongs that accidentally make a right” maneuver.

not exactly (if i understand it correctly). the first swap of a pair, where i < j, basically does not matter, since the same pair will be revisited one more time later with switched values (i = 8, j = 9 does not matter. i = 9, j = 8 does) and that is when the actual sorting happens. that is why the condition is if a[i] < a[j] then swap, which may seem countreintuitive, but we are comparing the values in the reversed order compared to most of the sorting algorithms.

the i < j part can be seen as the part that is handled in bubble sort by making the inner loop progressively smaller as the array is partially sorted (not the same elements, but the same amount of work, sort of). it is just ignored here, which is obviously bad for any kind of efficiency, but it allows for that super simple code.