“There is nothing good about this algorithm. It is slow – the algorithm obviously runs in Θ(n2) time, whether worst-case, average-case or best-case. It unnecessarily compares all pairs of positions, twice (but see Section 3). There seems to be no intuition behind it, and its correctness is not entirely obvious. You certainly do not want to use it as a first example to introduce students to sorting algorithms. It is not stable, does not work well for external sorting, cannot sort inputs arriving online, and does not benefit from partially sorted inputs. Its only appeal may be its simplicity, in terms of lines of code and the “symmetry” of the two loops.”
petercooper 6 hours ago [-]
On the topic of fun small sorting algorithms, I was always tickled by "sleep sort":
I thought of adding a timer to show it runs in a few ms but adding a timer would kind of defeat the purpose :)
fwlr 4 hours ago [-]
There are two reasons it (intuitively) should not work: one is that the inner for loop also starts from the beginning, without checking where the outer for loop is at, meaning you’ll get `compare(a[0], a[2]) == true` but you’ll also get `compare(a[2], a[0]) == false`, so it would appear you can’t get any useful meaning out of the result of `compare`. The other is that the comparison sign is the wrong way around.
Somehow, though, these two reasons it shouldn’t work manage to interact in a way that precisely counteract each other, producing a working sort!
senfiaj 5 hours ago [-]
Looks like suboptimal insertion sort.
After the first nested loop run A[1] will have the largest value.
After the second nested loop run A[1] will always be swapped with A[2] (unless they are equal, logically doesn't change anything). A[2] now contains the largest value.
After the k-th (k >= 2) nested loop run, if you pay attention, the k-th element will be inserted into the first k-1 sorted elements. When j >= i, it can no longer do anything, since A[k] will contain the largest value.
After the k-th (k >= 2) nested loop run the first k elements will be sorted relative to each other. The first nested loop is special by bringing the largest element to A[1], the consecutive ones are just inserting A[k] into the sorted first k - 1 elements from the beginning of the array.
The reason it works is because you get redundancy with everything referencing everything else. It looks like one of those CPU core to core latency diagrams. Without iterating like this the sort could only flow in one direction. If we modified the conditional to handle both cases you could split the square along the identity diagonal and only use half.
amelius 7 hours ago [-]
I'd like to see a formal proof of this.
Not because I don't believe it's true, but because this might be a nice entry into formal proofs.
This might be a nice entry into a class about algorithm optimization. You start with an easy-to-understand algorithm and point out where it can be optimized until you get a much faster one.
It's hard to imagine how many times this sort must've been written by accident (see the infinite monkey theorem). Imagine a CS student typing this while not entirely knowing what they're doing, presenting it to their instructor, getting told that the code is wrong and changing it to a proper bubble or selection sort without suspecting a thing.
7 hours ago [-]
6 hours ago [-]
6 hours ago [-]
VMG 7 hours ago [-]
I can't believe some people can read grey text on slightly lighter grey background
bajard 5 hours ago [-]
Right-click on the page > Select All.
VMG 2 hours ago [-]
I prefer right click on page > back
virajk_31 5 hours ago [-]
"you won't think that it can actually sort" - it does and anyone can tell the same by just looking at it...
efitz 5 hours ago [-]
Yes, the name seems like click bait. It’s pretty obviously a sort function, inefficiency notwithstanding.
6 hours ago [-]
bajard 5 hours ago [-]
In simple terms, this is the algorithm:
Repeat n times: sort all n pairs of elements.
7 hours ago [-]
ivanjermakov 7 hours ago [-]
It is very efficient, just for arrays not larger than 2 elements :)
iagiagiag 6 hours ago [-]
It's more confusing in your head than what the code looks like.
david-gpu 6 hours ago [-]
It has some redeeming qualities.
I would guess its running time is as consistent as the memory hierarchy allows. Having tight bounds on execution can be valuable in real time systems.
Simple to verify that the implementation is correct. Simple to implement in assembly.
Could be worse! I still prefer bogosort.
bajard 5 hours ago [-]
It has some cache locality that may make it beat smarter algorithms for certain arrays. For example, it can perform a lot of swaps while an O(n log n) algorithm is waiting for data to be fetched from memory.
Of course, an O(n log n) algorithm can also be optimized for cache locality.
logicallee 7 hours ago [-]
I'm pretty impressed by both Grok's and Gemini's static analysis of it. (I changed the name of the function to algo and asked them to figure out if it's supposed to be a sort algorithm or a search algorithm. Both got it right.)[1] If someone else could please check the same prompt on ChatGPT and Claude (which I don't have) please link.
I checked Sonnet, Mistral (GLM-5) and ChatGPT (GPT-6) with my own prompt, free version. They all get it if they have enough time (Claude checks the paper, ChatGPT and Mistral check with python code). But otherwise Mistral and GPT thought it would sort in descending order. I think when they understand it's a trick question they can automatically trigger additional reasoning / tools and come up with the correct answer.
logicallee 4 hours ago [-]
Thanks. Can you share the link to your chats? I'd love to look at their output.
Also, I pasted the incorrect grok link, this is the correct link:
Just to be clear, the author's intention wasn't really unclear! I just said "determine if it is intended to be a sort algorithm or a search algorithm (the author's intention might be unclear)" to force Grok/Gemini to really analyze it, in reality it's clear that it is a search algorithm. I also changed the word iCantBelieveItCanSort in the function name to algo to further make sure that Grok/Gemini really analyzed it, since the function name made it clear what it does.
7 hours ago [-]
gostsamo 7 hours ago [-]
search algorithms have a term to search and condition to stop, don't they? more like ask them to find what the function is meant to do, but the swap and comparison point to sorting pretty hard.
logicallee 4 hours ago [-]
yes, you're right. I wanted to see if Gemini and Grok got it, and they did.
Really fun video. There's a small mistake in the pseudocode in the video, where the indices are compared instead of the elements. Regardless, when he goes to demonstrate it he does compare the actual element values.
In that demonstration it seems like you can divide each pass into two parts: where i comes before j, and where i comes after j. It seems that only the pass where i comes after j (which is the first half) actually does something useful, the other half seems to sort it the opposite way, which then gets undone with the possibility to change it back being removed (since "i" has moved on permanently).
I suspect you could leave that second half out without changing the result. But if you only consider that first part (of sorting it "oppositely" to the comparison until the other index), it becomes equivalent to bubble sort.
Arainach 7 hours ago [-]
It's not, but it's conceptually very similar at first glance.
One important thing to note is that bubble sort places one element in the correct position each pass and then *stops looking at that position ever again*.
This algorithm looks at all N elements every pass.
Others have shared a bunch of great videos and writeups. Without reading them, my initial assumption is that this builds things bottom up (such that after the first pass, the element in position 0 is guaranteed to be the lowest element) and that despite it being compared again and again, it's essentially placing one element each pass, but I could be wrong.
whizzter 7 hours ago [-]
Technically the first pass will ensure that the smallest element ends up at position 0 even if it's looked at more times.
Bubblesort really is a family of "this is something I figured out myself that runs by looping in O(N^2) by moving things to the front/back"
pcthrowaway 7 hours ago [-]
> Technically the first pass will ensure that the smallest element ends up at position 0 even if it's looked at more times
Read it again; First pass ensures that the largest element ends up in position 0. Yet it somehow manages to sort ascending by the end.
It's not very intuitive and it's probably the least efficient sorting algorithm I've seen besides sleepsort[1]
Ah missed the part about the "swapped" equality, well since I will go ahead of J later on it's all good! :P
7 hours ago [-]
amelius 7 hours ago [-]
The hint is in the "<" operator.
stavros 7 hours ago [-]
It took me a while, but the surprising part is that the inner loop goes back to the first element again, unlike bubble sort which never revisits the outer loop's elements. So, at some point you'll compare element 3 with element 1, and swap so that 3 is smaller than 1, which is surprising.
senfiaj 2 hours ago [-]
No, it's not even selection sort, it's inefficient insertion sort with unintuitive logic.
That was my first instinct as well. But if you look closer you will see, it's actually insertion sort by someone who didn't pay attention in class.
It misses the revelation you can skip already sorted positions when deiciding what goes in the next position.
Btw. Ofcourse it sorts, it's basically insertion sort with extra swaps.
rcxdude 8 hours ago [-]
Look at it more carefully. Just reading the code, you'd think someone got confused between insertion sort and bubble sort and made a mashup that can't possibly work. But it still does.
Muhammad523 2 days ago [-]
No, it's not. There's a science paper with 3 theorems that prove it actually does sort
enjoyyourlife 2 days ago [-]
Bubble sort can sort
Muhammad523 22 hours ago [-]
Every other sorting algorithm does, by definition
mesrik 6 hours ago [-]
Well, mostly yes though some are less effective and may surprise time it takes to complete :)
"Two versions of this algorithm exist: a deterministic version that enumerates all permutations until it hits a sorted one, and a randomized version that randomly permutes its input and checks whether it is sorted.
An analogy for the working of the latter version is to sort a deck of cards by throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted. In a worst-case scenario with this version, the random source is of low quality and happens to make the sorted permutation unlikely to occur."
Jyaif 8 hours ago [-]
it's bubble sort without the early return.
[edit: my bad, it's not bubble sort]
rcxdude 7 hours ago [-]
Pull up the pseudocode for bubble sort and compare it.
“There is nothing good about this algorithm. It is slow – the algorithm obviously runs in Θ(n2) time, whether worst-case, average-case or best-case. It unnecessarily compares all pairs of positions, twice (but see Section 3). There seems to be no intuition behind it, and its correctness is not entirely obvious. You certainly do not want to use it as a first example to introduce students to sorting algorithms. It is not stable, does not work well for external sorting, cannot sort inputs arriving online, and does not benefit from partially sorted inputs. Its only appeal may be its simplicity, in terms of lines of code and the “symmetry” of the two loops.”
https://onlinegdb.com/VJ_0JKlQys
I thought of adding a timer to show it runs in a few ms but adding a timer would kind of defeat the purpose :)
Somehow, though, these two reasons it shouldn’t work manage to interact in a way that precisely counteract each other, producing a working sort!
After the first nested loop run A[1] will have the largest value.
After the second nested loop run A[1] will always be swapped with A[2] (unless they are equal, logically doesn't change anything). A[2] now contains the largest value.
After the k-th (k >= 2) nested loop run, if you pay attention, the k-th element will be inserted into the first k-1 sorted elements. When j >= i, it can no longer do anything, since A[k] will contain the largest value.
After the k-th (k >= 2) nested loop run the first k elements will be sorted relative to each other. The first nested loop is special by bringing the largest element to A[1], the consecutive ones are just inserting A[k] into the sorted first k - 1 elements from the beginning of the array.
Not because I don't believe it's true, but because this might be a nice entry into formal proofs.
Tick insertion sort on right panel and tap start.
Repeat n times: sort all n pairs of elements.
I would guess its running time is as consistent as the memory hierarchy allows. Having tight bounds on execution can be valuable in real time systems.
Simple to verify that the implementation is correct. Simple to implement in assembly.
Could be worse! I still prefer bogosort.
Of course, an O(n log n) algorithm can also be optimized for cache locality.
[1]
https://grok.com/share/c2hhcmQtMw_77a3a16f-642c-4ea7-95c7-28...
and
https://share.gemini.google/HADqPiEaeHQ9
Also, I pasted the incorrect grok link, this is the correct link:
https://grok.com/share/c2hhcmQtMw_542a51e1-64da-4e64-9353-c0...
Just to be clear, the author's intention wasn't really unclear! I just said "determine if it is intended to be a sort algorithm or a search algorithm (the author's intention might be unclear)" to force Grok/Gemini to really analyze it, in reality it's clear that it is a search algorithm. I also changed the word iCantBelieveItCanSort in the function name to algo to further make sure that Grok/Gemini really analyzed it, since the function name made it clear what it does.
In that demonstration it seems like you can divide each pass into two parts: where i comes before j, and where i comes after j. It seems that only the pass where i comes after j (which is the first half) actually does something useful, the other half seems to sort it the opposite way, which then gets undone with the possibility to change it back being removed (since "i" has moved on permanently).
I suspect you could leave that second half out without changing the result. But if you only consider that first part (of sorting it "oppositely" to the comparison until the other index), it becomes equivalent to bubble sort.
One important thing to note is that bubble sort places one element in the correct position each pass and then *stops looking at that position ever again*.
This algorithm looks at all N elements every pass.
Others have shared a bunch of great videos and writeups. Without reading them, my initial assumption is that this builds things bottom up (such that after the first pass, the element in position 0 is guaranteed to be the lowest element) and that despite it being compared again and again, it's essentially placing one element each pass, but I could be wrong.
Bubblesort really is a family of "this is something I figured out myself that runs by looping in O(N^2) by moving things to the front/back"
Read it again; First pass ensures that the largest element ends up in position 0. Yet it somehow manages to sort ascending by the end.
It's not very intuitive and it's probably the least efficient sorting algorithm I've seen besides sleepsort[1]
[1]: https://www.reddit.com/r/programminghorror/comments/lgsd18/i...
https://news.ycombinator.com/item?id=50516743
It misses the revelation you can skip already sorted positions when deiciding what goes in the next position.
Btw. Ofcourse it sorts, it's basically insertion sort with extra swaps.
https://en.wikipedia.org/wiki/Bogosort
"Two versions of this algorithm exist: a deterministic version that enumerates all permutations until it hits a sorted one, and a randomized version that randomly permutes its input and checks whether it is sorted.
An analogy for the working of the latter version is to sort a deck of cards by throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted. In a worst-case scenario with this version, the random source is of low quality and happens to make the sorted permutation unlikely to occur."
[edit: my bad, it's not bubble sort]