Join devRant
Do all the things like
++ or -- rants, post your own rants, comment on others' rants and build your customized dev avatar
Sign Up
Pipeless API
From the creators of devRant, Pipeless lets you power real-time personalized recommendations and activity feeds using a simple API
Learn More
-
Still, big O and computational complexity do not take real world implementations as input.
Radix sort is, of course, not comparison based, and is O(n), but that's amortized O(n). The cost of the hashing is hidden by the implicit k in O(k•n).
Same way that in modern c++, a vector surpasses a set in performance (even in operations designed for a set), up to several thousands of elements, just because it exploits cache locality si much better. -
@atheist returning the first element is guaranteed to lose data. Stalin sort losing data isn't predetermined.
There is a mAtHeMaTicAl pRoOf 🤡 that a comparison-based sorting algorithm cannot get more efficient than O(n*log n). That's bullshit. Radix sort et al. — granted, they're not comparison-based.
But there is one comparison-based algorithm that can sort an array in O(n). It's called Stalin sort.
It traverses the array and deletes every item that doesn't appear in order. Boom, problem solved — the array is sorted in O(n), at the expense of losing (most of the) elements.
This is the perfect metaphor of Stalin's politics.
joke/meme