Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The unreasonable effectiveness of modern sort algorithms

github.com

Post reply on HN
Print view View original

31–40 of 62 posts

Re: The unreasonable effectiveness of modern sort algorithms

#31

Post by Imnimo »

lukaslalinsky wrote: post #20

There is one sentence I really took out from the years at university, it was at a database implementation course: > If you have a trouble solving some problem, see if sorting the data first helps. I feel that sorting data is the ultimate computer science hack. Many, many, classes of problems turn into O(log n) problems, once you sort your input in some way. It might not be the most effective way of solving the proble…

Just be careful you aren't doing the classic, "my linear regression works way better when I independently sort the inputs and targets"!

Re: The unreasonable effectiveness of modern sort algorithms

#32

Post by wizardforhire »

lukaslalinsky wrote: post #20

There is one sentence I really took out from the years at university, it was at a database implementation course: > If you have a trouble solving some problem, see if sorting the data first helps. I feel that sorting data is the ultimate computer science hack. Many, many, classes of problems turn into O(log n) problems, once you sort your input in some way. It might not be the most effective way of solving the proble…

Side note: this works great for fermions as well…

To save the densest among you the oh so tedious task of extrapolation here are a some anecdotal examples.

Dishwasher: Sort your dishes when you pull them out. Cut your walking time to the minimal possible steps, think of this like accessing cache data. Enjoy the now painless benefit of constantly clean dishes and kitchen.

Short story: Some friends had a geodesic dome company. I’d get brought out to do setup when they were really busy. These Domes had a lot of heavy metal pipes of different and specific lengths. Its hot, it’s outside, its heavy and tedious… pipes would invariably be in a giant pile on a pallet… caught another friend doing bubble sort… the 56’ dome went up in record time with the two of us.

More meta-hierarchical: End of life, parents on cusp of hoarding. Trauma combined with sentimentality manifests as projecting value on to items. Items pile up, life becomes unmanageable, think of this like running out of ram. Solution: be present, calm and patient. Help sort the memories and slowly help sort the items. Word of warning this is NP-hard-af… eventually they will get out of it and the life for them and you will dramatically improve.

Further reading: https://knolling.org/what-is-knolling

Re: The unreasonable effectiveness of modern sort algorithms

#33

Post by boothby »

lukaslalinsky wrote: post #20

There is one sentence I really took out from the years at university, it was at a database implementation course: > If you have a trouble solving some problem, see if sorting the data first helps. I feel that sorting data is the ultimate computer science hack. Many, many, classes of problems turn into O(log n) problems, once you sort your input in some way. It might not be the most effective way of solving the proble…

It's funny because the opposite is often true as well: if you're having trouble solving a problem quickly, randomize the data and try again.

Re: The unreasonable effectiveness of modern sort algorithms

#34

Post by [deleted] »

boothby wrote: post #33
lukaslalinsky wrote: post #20

There is one sentence I really took out from the years at university, it was at a database implementation course: > If you have a trouble solving some problem, see if sorting the data first helps. I feel that sorting data is the ultimate computer science hack. Many, many, classes of problems turn into O(log n) problems, once you sort your input in some way. It might not be the most effective way of solving the proble…

It's funny because the opposite is often true as well: if you're having trouble solving a problem quickly, randomize the data and try again.

[deleted]

Re: The unreasonable effectiveness of modern sort algorithms

#35

Post by throwaway81523 »

lukaslalinsky wrote: post #20

There is one sentence I really took out from the years at university, it was at a database implementation course: > If you have a trouble solving some problem, see if sorting the data first helps. I feel that sorting data is the ultimate computer science hack. Many, many, classes of problems turn into O(log n) problems, once you sort your input in some way. It might not be the most effective way of solving the proble…

I spent many years as a programmer somehow avoiding ever doing much with databases, since most problems that seemed to want databases could instead be solved using sorting batch-collected data.

Re: The unreasonable effectiveness of modern sort algorithms

#36

Post by chuckadams »

kwertyoowiyop wrote: post #17
creata wrote: post #11

Earlier quoted context omitted.

"The Unreasonable Effectiveness of Mathematics in the Natural Sciences" is one of those titles that gets imitated a lot for some reason. Maybe even more than "Goto Considered Harmful".

Coming next: “What we talk about when we talk about modern sort algorithms”

"Optimize your sorts with this one weird trick."

"What they don't want you to know about sorting."

Re: The unreasonable effectiveness of modern sort algorithms

#37

Post by TuxSH »

lukaslalinsky wrote: post #20

There is one sentence I really took out from the years at university, it was at a database implementation course: > If you have a trouble solving some problem, see if sorting the data first helps. I feel that sorting data is the ultimate computer science hack. Many, many, classes of problems turn into O(log n) problems, once you sort your input in some way. It might not be the most effective way of solving the proble…

> Many, many, classes of problems turn into O(log n) problems, once you sort your input in some way. It might not be the most effective way of solving the problem, but it's often a fairly good one.

As a corollary, you can use binary search+linear interpolation as a fast way to approximate a strictly monotonic function, knowing its reciprocal, over a limited sets of outputs (e.g. n -> floor(255 * n^(1/2.2) + 0.5) for n in 0..255). You also get to work on bit_cast(...) as an optimization when the targeted FPU doesn't have conditional move instructions.

Re: The unreasonable effectiveness of modern sort algorithms

#38

Post by Animats »

Neat.

Adaptive radix sorts exist, where the keyspace is divided into roughly equal sized buckets based on the distribution of the data. The setup is slow enough that this is usually used only for very large sorts that have to go out to disk, or, originally, tape.

It's the first patented algorithm, SyncSort.

Re: The unreasonable effectiveness of modern sort algorithms

#39

Post by forsalebypwner »

allturtles wrote: post #29

The scenario presented seems very odd. Why would you want to sort 10^7 items that are known to contain only four distinct values? It seems much more likely you would be counting the number of times each value appears, or selecting all of the elements of value X.

I believe the purpose of choosing such an odd scenario is to show that, while you might think that you can beat the generic sort algos with a more domain-specific implementation, you might be wrong, or you might not gain enough performance to make it worth the other pitfalls of using such algos

Re: The unreasonable effectiveness of modern sort algorithms

#40

Post by RyanHamilton »

lukaslalinsky wrote: post #20

There is one sentence I really took out from the years at university, it was at a database implementation course: > If you have a trouble solving some problem, see if sorting the data first helps. I feel that sorting data is the ultimate computer science hack. Many, many, classes of problems turn into O(log n) problems, once you sort your input in some way. It might not be the most effective way of solving the proble…

Similar to you, based on years with databases I saw sorting as a huge advantage and often performed this step as part of optimizing any data access. I've tended to see the same pattern of problems over the last 15 years. Imagine my surprise when I read a blog post that showed not perfectly sorting your data could often result in faster overall result time for a wider range of queries. Duckdb: https://duckdb.org/2025/06/06/advanced-sorting-for-fast-sele... continues to surprise me with novel improved approaches to problems I've worked on for years.
Post reply on HN