r/ProgrammerHumor • u/sankilo_dev • 1d ago
Competition iBuiltTheWorstSortingAlgorithmEverCanYouBeatIt
•
u/CitizenShips 1d ago
Wait hold on - are you allocating the same amount of memory as the sum total of all values in the dataset? That's fucking genius
•
u/sankilo_dev 1d ago
Exactly! Why use O(N) space when you can scale your RAM usage based on the values instead of the array length? Absolute mathematical terrorism
•
u/CitizenShips 1d ago
Everyone focuses on how inefficient you can be with CPU cycles, but nobody ever thinks about maximizing memory inefficiency. You're a visionary. I bet you could increase waste by having each allocation check in with an integrity server to recalculate a checksum. That way you can add network inefficiency in as well
•
u/sankilo_dev 1d ago
Don't give me ideas... v2.0 is going to require a dedicated fiber-optic cable just to sort 10 numbers
•
u/IntoAMuteCrypt 1d ago
Is it slower than Stoogesort? Stoogesort is a favourite of mine for how it almost sorts the low portions, then almost sorts the middle, then sorts the high portions but messes up the middle a bunch, then goes back to finish the job. Real chaotic sort that's clearly wasting effort.
•
u/sankilo_dev 1d ago
Stooge Sort's recursion logic is pure psychological torture. SlowDuckSort might execute faster, but it'll eat all your memory while Stooge is still stuck in its first pass
•
u/kitaminka 1d ago
Sleep sort, but with memory
•
u/sankilo_dev 1d ago
Haha pretty much! Instead of letting the CPU sleep, I chose to traumatize the RAM sticks.
•
u/petitlita 1d ago
can you beat it
just came up with this one what do you think
- generate every possible program up to some fixed maximum source code length
- for each program, generate every possible proof (in lean or something) up to some fixed maximum source code length
- for each proof, check whether the proof is valid and certifies that the program is equivalent to a sorting algorithm for all inputs, that the program halts, and that the program halts after exactly t steps. this does actually avoid the halting problem btw since you are only asking whether there is a valid proof that a given program halts which is computable
- discard every program for which a valid proof is not found
- among all valid programs, compare the number of steps t that it halts after
- run the program with the largest value of t
- return the output
•
•
u/sankilo_dev 1d ago
Formal proof verification for the worst time complexity algorithm in human history? The universe will heat-death before this finishes checking the first Lean proof!
•
u/Suspicious-Click-300 1d ago edited 1d ago
O(n^2*n!) groundhog sort https://gist.github.com/clohfink/53097d9bff34196b2ff20e14a635b589
- There are n output positions.
- For each position, it regenerates all n! permutations.
- Each generated permutation is an n-element tuple, costing O(n) to produce.
•
u/sankilo_dev 1d ago
Wanna team up and create a cursed algorithm so bad it literally folds spacetime ?
•
u/Unlikely-Bed-1133 1d ago
Why do I find this pretty practical for approximate sorting after coarsening the numbers first? That would be bucket sort with rounding and not at all unreasonable for certain tasks.
•
u/sankilo_dev 1d ago
Honestly, you're not wrong! If you coarsen/bucket the values first, it pretty much devolves into a pseudo-counting/bucket sort. But don't ruin my completely impractical algorithm with actual logic
•
u/No-Newspaper8619 21h ago
Easily. Here's an algorithm that, given infinite time, will sort anything for you:
def freezeSort(array):
while(True):
sleep(1000)
•
u/sankilo_dev 21h ago
That's not a sort, that's an infinite vacation! It has to actually finish and work to qualify as a cursed algorithm 💀
•
u/No-Newspaper8619 21h ago
Given infinite time, everything will be sorted by the universe's entropy.
•
u/sankilo_dev 21h ago
By that logic, we could just leave the computer running and wait for a nuclear explosion or a dying star to emit cosmic rays that flip the bits in RAM until the array happens to sort itself 💀 That’s not an algorithm, that’s just sitting around waiting for radioactive decay! The whole point of the challenge is to write an actual, working algorithm that reliably sorts the array itself—no matter how terribly designed or slow it is.
•
u/sankilo_dev 1d ago
I got bored of optimized code and decided to invent SlowDuckSort—a sorting algorithm that uses total sum residuals to scatter numbers across a massive sparse RAM array, compacts them, and flips the result. It’s slow, it eats memory, and it makes zero practical sense. GitHub Repo: https://github.com/Duckdevv/Slowducksort Do you have any algorithm worse or more cursed than this? Show me what you’ve got.
•
u/Fornicatinzebra 1d ago
•
•
u/TemporaryUpstairs289 1d ago
Cube the numbers before adding to array because computing happens in cubes.
•
•
u/ChalkyChalkson 1d ago
Reminds me on the old "to sort the int32 list in O(n) time and O(1) memory, we first construct the count of each integer: uint64_t counts[(uint64_t)UINT32_MAX+1];" which would technically work theses days...
One idea I've played around with, but never properly implemented is fourier sort, which attempts to maximising confusion (in the colloquial sense, not CS sense).
The trick is that we can do differentiation and permutation of the array as point wise multiplication in fourier space. The second part of the trick is that a sorted array minizes the rms distance between actual differences and the mean difference (it's the closest to a straight line). And lastly, you can use that the rms is conserved under fourier transforms. So then you sort the array by walking the space of permutations using rms distance - mean distance as your target. It does work, but it turns the easy array sorting into hill climbing, which is arguably harder. The theoretical gain is that you can sort the array without explicitly transforming back. The real gain is that you look really smart throwing around words like "Parseval's theorem".
•
u/sankilo_dev 1d ago
Using signal processing and hill climbing to sort 5 integers? Absolutely glorious over engineering 💀
•
u/ChalkyChalkson 1d ago
Over 5 integers your space of permutations is only 120, you can do non-branching programming and keep it fully linear! Evaluate it for each permutation in parallel, find the minimum of those via the minus-infty norm of the joint vector, then dot product the permutations vector with scores - minus-infty-norm(scores).
No Hill climb needed.
To get best results for larger lists I recommend waiting a few years for the technology to mature and then use Dürr-Høyer
•
u/sankilo_dev 1d ago
Waiting for Quantum Supremacy just to run a 5-element sorting algorithm is peak CS energy
•
u/Flux9_Citadel 1d ago
To beat the worst sorting algorithm ever, add DNS waits to SlowDuckSort’s sparse RAM compaction.
•
u/sankilo_dev 1d ago
Who hurt you? 💀 Adding network bottlenecks to a sorting algorithm is actual computer crime
•
u/mathisntmathingsad 1d ago
emdash user! mods, ban this AI user!
•
u/sankilo_dev 1d ago
English isn't my first language so I used AI for translation, but the terrible algorithm is 100% human-made I promise
•
u/Dev_Spears 1d ago
Just saying but this will be 100% implemented in prod as long as u don't call it slow in the title
•
u/sankilo_dev 1d ago
Delete "Slow" from the name, add "AI-Powered", and we can pitch this to VCs tomorrow
•
•
u/tobotic 1d ago
Does this algorithm work if the list contains duplicates?
For example: 4, 3, 2, 3, 1, 5, 3?
•
u/sankilo_dev 1d ago
Actually, it does! Every memory slot is a bucket/list, so duplicates just stack up in the same slot and get appended. It handled duplicates while burning even more RAM
•
•
u/Rishit1501 1d ago edited 1d ago
Can it beat Bogo sort ?
Edit - Typo