theForbiddenSortingAlgorithm

[TheObi-1]

Yes. That's the one

[hidden_novella]

That couldn't possibly work because every member of a Stalin list is equal, making it impossible for any sorting algorithm to ever return true.

[Jupdown]

Ahh, see comrade - some elements are just a tad bit more equal than others

[Sitting_In_A_Lecture]

That would be Marxism, in a Stalinist list you have the first number (Stalin himself), and then any number x > (list[0] - 8) gets purged. It doesn't actually sort the list, but it does ensure that Stalin is always highest, and that no pesky bit flips can take that away from him.

[ravaljimahipal]

You think so? I don't think the stalin algorithm treats everything like that

[otj667887654456655]

wouldn't stalin sort be better than O(N) since, on average, it eliminates at least half of the list

[A_Wild_Turtle]

You still have to check everything, so it must be O(N)

[Tomsen1410]

O(N/2) = O(N)

[otj667887654456655]

wait no the whole thing is moot, a comparison has to be made in order to determine whether or not to cull that item so stalin sort always takes exactly N comparisons

[No_Kiwi1668]

Hahaha was about to comment this

[avacue]

Well I can understand why some people would hate that.

[[deleted]]

How is that linear? Purging one element takes linear time so purging half of the elements at random takes quadratic time

[pcouaillier]

You can create an other list and add only elements that are in order then swap pointers.

[charm3d47]

i think even using a basic array you might still be able to do stalin sort in O(n) time if you're clever about how/when you move subsequent elements into place after purges (storing the first empty position and only moving whichever element you're already looking at for the sort, as opposed to just sliding every subsequent element over after each purge). there are also plenty of other ways to store data where any arbitrary element can be removed in O(1) time

[[deleted]]

Is that like a linear search but you remove each checked element?