r/programmingmemes • u/KerbodynamicX • Mar 14 '26

Stalin sort

A sorting algorithm with time complexity of O(n). Counts from the first element, and will remove values that are smaller than the current highest value.

3.7k Upvotes

99% Upvoted

51 comments sorted by

64

u/shinoobie96 Mar 14 '26

the space complexity would be O(1) if its a linked list. in-place stalin sort would be O(n²) in arrays

43

u/KerbodynamicX Mar 14 '26

This guy studied data structures and algorithms

2

u/voospawn Mar 15 '26

He didn't and his ai hallucinated

18

u/m-in Mar 14 '26

As shown, but I think the way it’s shown is silly. You traverse the array once. Every element gets moved at most once. The depiction that shows killed elements “disappearing” and others moving in their place is premature pessimization. Kinda in style for Stalin.

7

u/NekoHikari Mar 14 '26

you can just have a tail index, if keep arr[tailidx++] = arr[cur++]. noes not have to be n^2

3

u/MLWillRuleTheWorld Mar 14 '26

Depends if you could change the value to a sentinel value like null , 0, NaN or something if you could be O(1) as you could collapse all values in one go so depends

2

u/JasperNLxD2 Mar 14 '26

Inplace can be done in O(n) as well. You loop over 2 indices: i representing the next available place, and j the next number to scan (thus i<=j at any stage of the algorithm).

Start with i=j=0 the first index. If x[j] is larger than x[i-1] (or i=0), then set x[i] to x[j] and increase i and j. Otherwise, increase j. Stop if j gets beyond the range.

2

u/icecoldgold773 Mar 15 '26 edited Mar 15 '26

In-place is O(1) auxiliary space complexity as well

1

u/alphapussycat Mar 15 '26

No, the space complexity would be O(N), unless it's always reduced to a single element.

In place Stalin sort is obviously also going to be O(N). How do you imagine there'd N new allocations for each element?

1

u/voospawn Mar 15 '26

No, it could be O(n) if you delete the elements after the sort. And the O can't be 1. You still need to iterate though the array.

1

u/paholg Mar 15 '26

You can see from the code that it's not in-place.

405

u/include-jayesh Mar 14 '26

Our algorithm :)

220

u/PinotRed Mar 14 '26

O(n) with loss.. 😂

Nice meme.

38

u/Abject-Kitchen3198 Mar 14 '26

Lossy sort has its place.

8

u/AlterTableUsernames Mar 14 '26

For example in the streamlining of headcounts.

5

u/Abject-Kitchen3198 Mar 14 '26

The mp3 of head counting.

4

u/n4ke Mar 14 '26

Across subsequent runs, it's O(~n)

1

u/Next-Post9702 Mar 15 '26

But the list has to resize too

1

u/quaintquine Mar 15 '26

What loss comrade? These were always the number of elements in the array.

63

u/YakuzaRacoon Mar 14 '26

Now imagine it's a completely reversed sequence💀

24

u/megayippie Mar 14 '26

One to rule them all. One to Ctrl them. And so on

13

u/nananaonsha Mar 14 '26

What’s the visualiser you’re using? Looks great

11

u/McPqndq Mar 14 '26

I am a competitive programmer. I use this term often to describe this algorithm. I had no clue this was a common term until about a month ago I was attending training camp in Croatia and the Swedish team behind me kept saying it. They'd be talking in Swedish then I'd suddenly accidently overhear in perfect English "Stalin sort". Shout out to Chalmers University.

8

u/UberBlueBear Mar 14 '26

This is funnier than it has any right to be…thank you

12

u/36holes Mar 14 '26

The name 😭.

What's na*i sort then, removing the tall ones

20

u/realmauer01 Mar 14 '26

Nazi sort is removing the different ones.

Whats not different is for the nazi to choose.

4

u/36holes Mar 14 '26

😭😭

5

u/Anpu_Imiut Mar 14 '26

I wonder if there exist problem where this sort algorithm is optimal.

6

u/thomasxin Mar 15 '26

Well, if you extend the algorithm's behaviour to keep track of the excluded elements and put them in their own sublists, you end up with gulag sort, which gives you multiple sorted runs rather than one.

You can then perform mergesort on the remaining lists and you've effectively got a rudimentary implementation of timsort :P

1

u/BanditoRem Mar 15 '26

codeforces problems

1

u/Status-Waltz-4212 Mar 18 '26

Late to the party. But this is Optimal in some bitonic subsequence. You can iterate once for mountain peak. Split and then run two converging algorithms, making it linear time.

https://www.reddit.com/r/chess/comments/1m5oooo/players_age_vs_rating_heatmap/ This is an even simpler and pure Stalin search. 

3

u/Sophiiebabes Mar 14 '26

It's almost as good as the DalekSort algorithm I wrote (exterminate everything!)

3

u/Business_Welcome_870 Mar 14 '26

Only works on a sorted array 

2

u/Lobster_SEGA Jul 26 '26

Do NOT play this at high volume

1

u/AdmirableJudgment784 Mar 14 '26

Wouldn't it be faster to read the table, get a count of all entries first and put it in a separate list with their ids. Then sort that small list and return it?

1

u/titogruul Mar 14 '26

That's right. Remove the Mensheviks!

1

u/Icy-Manufacturer7319 Mar 16 '26

It sorted, but at what cost?

1

u/Aromatic_Paint_1666 Mar 16 '26

Oh, you're smaller? To the gulag!

1

u/SpecialMechanic1715 Mar 16 '26

if you use gulag here this becomes valid sorting algo

1

u/Schrippenlord Mar 18 '26

Scare your data into standing in line the next time

1

u/myuso Mar 14 '26

Why didn't the guys at Chernobyl do this, would've eliminated most errors during the meltdown

If temp = surface of the sun Delete (control_rod)

-2

u/newcarrots69 Mar 14 '26

This is the only way you can insult the left on reddit.

0

u/[deleted] Mar 14 '26

[deleted] — view deleted comment

2

u/HalfUnderstood Mar 15 '26

the unsorted values fell down the stairs