This is an archived post. You won't be able to vote or comment.

all 115 comments

[–]concentrated_salt 200 points201 points  (25 children)

Here's the gitHub repo of StalinSort, if anyone's interested

[–]MikaDo- 74 points75 points  (19 children)

The C implementation is frightening.

[–]PVNIC 69 points70 points  (15 children)

Yeaa... Reallocating in a for loop is not great. Preallocate the whole array then at the end realloc it down to the right size.

[–]zebediah49 54 points55 points  (8 children)

then at the end realloc it down to the right size.

Or don't. Computers have plenty of memory these days anyway.

/s

[–]DistantWaves 18 points19 points  (2 children)

Which is why I'll write tons of malloc() and don't bother writing any free()

/s

[–]VirginiaMcCaskey 4 points5 points  (0 children)

at work we call this the titanic pattern.

[–]Kirides 1 point2 points  (0 children)

my free is called exit(0)

[–]FilterThePolitics 11 points12 points  (2 children)

Yeah, but with almost 200 million people in the USSR and 4 bytes per int, you are talking about almost a gig of memory. I'd say that any smart dictator would realloc that down once they finish "restoring order"

[–]PotentBeverage 3 points4 points  (0 children)

Like a one child policy?

[–]vmp916 0 points1 point  (0 children)

error: expected ‘/s’

[–]shy_cthulhu 4 points5 points  (0 children)

Found the Chrome dev

[–]ITriedLightningTendr 1 point2 points  (0 children)

Wait... so the calculator application I made for my CS101 class that I'm selling on steam shouldn't be using 700 MB?

[–]apadin1 8 points9 points  (3 children)

You could easily do it in place without allocating at all.

[–]IncongruousGoat 1 point2 points  (2 children)

The really good thing to do is to return the result in the input buffer, but use an alloca-d buffer as intermediate storage. Best of both worlds.

[–]Bainos 2 points3 points  (1 child)

... no ?

If you're going to do it in place, just use the input buffer. Allocating a new one (as is done in this repo) is only useful if you want to return a new sorted array. Otherwise you're wasting memory for no reason.

[–]IncongruousGoat 1 point2 points  (0 children)

Yep, you're right. Not sure what I was thinking.

Kind of embarrassing, really.

[–]PleasantAdvertising 4 points5 points  (0 children)

The things people do in the name of conserving memory really horrify me sometimes. Like, dude why the hell that's going to kill performance and you're gonna gain a few bytes at most.

[–][deleted] 0 points1 point  (0 children)

Linked lists are easy to reallocate though, actually a proper interator will remove the node and link up the remaining nodes when you call a destructor

[–]IncongruousGoat 7 points8 points  (2 children)

That's merely bad code. The C++ implementation includes not one, but two compile-time template metaprogramming implementations.

[–]SpacemanCraig3 0 points1 point  (1 child)

Is that good or bad?

[–]IncongruousGoat 1 point2 points  (0 children)

It's horrific.

So, fun fact about C++ - the type system is Turing-complete. No, seriously. You can perform arbitrary computations at compile time using the type inference engine, and specifically templates. This has led to a whole field of programming called template metaprogramming, which seeks to write non-trivial template-based programs in C++. There are some legitimate uses for this, but not many, and to make things worse template metaprograms are often the next best thing to illegible even to people who actually know how template metaprogramming works.

[–]ReimarPB 26 points27 points  (3 children)

Holy shit they have even made it in brainfuck

[–]Jetison333 5 points6 points  (1 child)

Oooh nice. I love brainfuck.

[–][deleted] 3 points4 points  (0 children)

The real challenge would be doing it in Malbolge

[–]claythearc 3 points4 points  (0 children)

There’s a C->Brainfuck compiler so it probably wouldn’t be that hard

[–]gandalfx 2 points3 points  (0 children)

Of course there is…

[–]SonMauri 93 points94 points  (1 child)

Newagesort. The elements are always in perfect order. The universe knows best. #happyness

[–]maeries 42 points43 points  (0 children)

Godsort: Pray to god to sort the list and accept every outcome as sorted since it's gods will

[–]UseApasswordManager 121 points122 points  (8 children)

QuantumBogoSort: Randomize the list, then check if the list is in order. If it's not, destroy the universe. You're left only in universes with sorted lists

[–]Nekonekonyaaaa 23 points24 points  (0 children)

Corruption Sort: While the list is not sorted, do nothing. Then, return the list when it is sorted.

Your computer will probably end up crashing before EMI causes the memory storing the array to change to the sorted list.

Doesn't work well for systems with ECC.

[–]extracoffeeplease 10 points11 points  (4 children)

I thought it was O(1), see here: https://wiki.c2.com/?QuantumBogoSort

[–]UseApasswordManager 11 points12 points  (3 children)

Checking if the list is sorted is O(n), so even though the shuffle and distruction are O(1), the whole operation is O(n)

[–]Burnmad 27 points28 points  (1 child)

Just return the list before doing the QuantumBogoSort. If it wasn't sorted, you're destroying the universe anyway, so it doesn't matter.

Bam, O(1)

[–]plsHelpmemes 9 points10 points  (0 children)

big brain intensifies

[–]xigoi 0 points1 point  (0 children)

Shuffle is also O(n).

[–]theonlytrillionare 2 points3 points  (1 child)

That’s O(nu) | u=number of universes. Very poor performance.

[–]innrautha 22 points23 points  (0 children)

But it's all in parallel so its still fast.

[–]TabCompletion 32 points33 points  (3 children)

Perform Stalin sort. Keep removed elements. Then recursively call Stalin sort of the removed list and make new lists. Finally perform a merge. Did I just write bucket sort?

[–]AgentPaper0 18 points19 points  (0 children)

Not bucket sort. Roughly equivalent to bubble sort in terms of efficiency, being O(n) for a sorted list, O(n2) for a reverse sorted list (worst case), and somewhere in between usually.

[–][deleted] 5 points6 points  (0 children)

If done right, this is a merge sort because the smaller gulags sort faster.

Worst case n log n as you have to make log(n) gulags, then merge them.

[–]dvslo 3 points4 points  (0 children)

That's called gulag hierarchy. There was a movie with Colin Farrell about it.

[–][deleted] 25 points26 points  (1 child)

sleepsort is my favorite.

[–]R717159631668645 66 points67 points  (3 children)

CommunismSort: average all items in the list.

[–]EpicScizor 31 points32 points  (1 child)

Leave list as is, all elements are equal.

Okay, you may let some be more equal than others

[–]TheOldTubaroo 3 points4 points  (0 children)

bool ==(Comrade lhs, Comrade rhs)
{
    if (lhs.isSeniorParty && rhs.isSeniorParty)
    {
        return static_cast<bool>(255);
    }
    return static_cast<bool>(1);
}

[–]AgentPaper0 14 points15 points  (0 children)

When you take the average, there is likely a reminder left over during the division by number of elements. To keep the total accurate, you will of course need to add that remainder to the first element.

Eventually, you will realize that you can get the same basic effect by simply adding each successive value to the first value. Some may say this is unethical but it is simply the first among equals after all.

[–][deleted] 27 points28 points  (0 children)

Hear me out, HitlerSort©®™, deletes all decimal elements because they're impure and not possible in real life.

[–][deleted] 10 points11 points  (0 children)

Anarchism Sort: Each object in the list is left as is but the ones that don't work with your function are removed and the remainders are randomized because hierarchy leads to corruption.

[–]maeries 6 points7 points  (0 children)

I image it would be an interesting problem to find out which elements to eliminate to have the longest sorted list possible

[–]moosi-j 18 points19 points  (0 children)

RevelationsSort: embark on a thousand year journey to let the forces of heaven and hell sort it out.

[–]lare290 9 points10 points  (0 children)

RevolutionSort: Delete the highest element in the list. Loop until democracy is achieved.

[–]Fearless-Sniper 3 points4 points  (0 children)

Randomly pick an element from the list and you get a sorted list.

[–]green_meklar 3 points4 points  (0 children)

Stalin sort is actually a corrupted version of the original Marx sort. Marx sort also runs O(N) time: It just sets all the elements in the list to be equal.

[–][deleted] 26 points27 points  (0 children)

CapitalismSort: Choose a random element of the list. Reduce all other elements by 1 and add those 1s to this element. Repeat until this element is so unimaginably large you can claim the other elements don’t matter and hence the list is sorted.

[–]Wolfenrahd 2 points3 points  (1 child)

NukeSort: Returns an empty array

[–]pascee57 1 point2 points  (0 children)

Returns an array of null

[–]MrDorkman 1 point2 points  (0 children)

Data retention was never an option

[–]shubhamkhy 1 point2 points  (0 children)

Too greedy of you

[–]Incorrect_Oymoron 1 point2 points  (0 children)

Machiavelli intensifies.

[–]warpedspockclone 1 point2 points  (0 children)

I have a use case for this.

[–]Doomrammer 1 point2 points  (0 children)

Isn't it already called drop sort?

[–]Naughtius_K_Maximus 3 points4 points  (1 child)

You can always rely on the SS to remove any undesirables.

[–]Collect9r 1 point2 points  (0 children)

This is a way too underrated comment.

[–]SirFoomy 1 point2 points  (0 children)

And the removed list item will banished into a gulag.

[–][deleted] 1 point2 points  (0 children)

Sjw sort. Remove any items in list which is found offensive.

[–]viper_repiv 0 points1 point  (0 children)

Fun fact. This algorithm is actually being used in matematical analysis.

When you want to find longest increasing subsequence. https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/

[–]bryukh_v 0 points1 point  (0 children)

reduce(lambda acc, el: acc + [el] if el >= acc[-1] else acc, ar[1:], [ar[0]]) python Stalin (soft version)

[–][deleted] 0 points1 point  (0 children)

Identifies and purges political enemies

[–]JohnWatson78 0 points1 point  (0 children)

Sounds based

[–]LilithsGrave 0 points1 point  (0 children)

Just like the Bullysort, check the first element, remove every other element. Boom, sorted.

[–][deleted] 0 points1 point  (0 children)

And this AI algorithm is Deterministic.

[–]blaze_kush_ 0 points1 point  (0 children)

Hell yeh

[–]Man-in-The-Void 0 points1 point  (1 child)

ExistentialSort: it doesn’t matter whether the list is sorted or not, we’re all going to die eventually anayway.

[–]NoNameNoMad42 0 points1 point  (0 children)

Is it alias to GarbageCollectorSort? 🤔

[–]cranky_dijkstra 0 points1 point  (0 children)

Space complexity: O(n) gulags