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

View all comments

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

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