Hacker News new | past | comments | ask | show | jobs | submit

New book-sorting algorithm almost reaches perfection

https://www.quantamagazine.org/new-book-sorting-algorithm-almost-reaches-perfection-20250124/
"Kuszmaul remembers being surprised that a tool normally used to ensure privacy could confer other benefits."

It was surprising to me too! But reflecting on it more closely, most performance isn't about "faster" in a literal sense of "more instructions run per time", but about carefully choosing how to do less work. The security property here being "history independence" is also in a way stating "we don't need to, and literally cannot, do any work that tracks history".

It's definitely an interesting approach to performance, essentially using cryptography as a contraint to prevent more work. What properties do we need, and what properties can we ignore? The question becomes if we MUST ignore this property cryptographically, how does that affect the process and the related performance?

It certainly feels like it may be a useful perspective, a rigorous approach to performance that may be a path to more improvements in key cases.

loading story #42818888
loading story #42817571
loading story #42817101
loading story #42815822
Am I the only one that's trying to find the main papers that're being described in the article both the original problem, and the near optimal algorithm paper [1],[2].

Apparently both of them are linked deep inside the article, perhaps Quanta can make it mandatory to list all the reference towards the end of the article, it will be very helpful for the readers.

[1] Nearly Optimal List Labeling:

https://arxiv.org/abs/2405.00807

[2] A sparse table implementation of priority queues:

https://link.springer.com/chapter/10.1007/3-540-10843-2_34

loading story #42825621
I was actually just looking at this problem last week, when I realized I needed to keep items in a database table positioned arbitrarily, ideally without needing to manipulate the rest of the list. So if a user adds in a new element after element 5, that element becomes 6, without needing to update the original item that came after element 5. There are indeed very sophisticated algorithms to manage this problem and minimize theoretical bounds. But it also seemed like the simplest solution for this particular version of the problem is to just use fractional amounts, and occasionally pay a penalty to relayout the list.
loading story #42815845
loading story #42815595
loading story #42815251
loading story #42820254
loading story #42814755
loading story #42820400
I recall presenting a problem to my students a few years ago based on the 'Library Sort' algorithm. I still clearly remember the title of the original paper: 'Insertion Sort is O(n log n)'.
loading story #42815519
loading story #42815772
Is there any reason to think that this algorithm will actually be faster than what is currently done in practice?

For arrays in B-tree nodes, which is the main place where I have encountered this problem, I doubt it will be faster than just using `memmove()`, and for truly large arrays, it would be easier to use a B tree.

If that is the case, this joins a number of algorithms that are asymptotically faster than algorithms in use and paradoxically slower than them. Examples of such algorithms include all of the fast matrix multiplication algorithms, which are slower than good implementations of the the textbook O(n^3) algorithm (GEMM).

loading story #42817493
> lowering the upper bound to (log n) times (log log n)^3 — equivalent to (log n)^(1.000...1)

This is true! One of the things I find cool about big-O complexity using polynomial reference classes is that logarithms give you an infinitesimal value. Take that, "infinitesimals don't really exist" people!

loading story #42817659
I was shocked to discover how the British Library (millons of books, many many new ones every week) manages this. The first book to arrive earlier this year went on the shelf at 2025.0000001. The next went at 2025.0000002, right next to it. The electronic catalogue does the rest. No need to re-shuffle books around, but not a solution supportive of book-browsing.
loading story #42816762
Off topic, but now I want a screen saver of the animation at the top of the article...
Clean links for mobile users

Game: https://patorjk.com/games/subpixel-snake/ Code: https://github.com/patorjk/subpixel-snake

Resource for subpixel geometries: https://geometrian.com/resources/subpixelzoo/

loading story #42816320
loading story #42816280
I’m trying to figure out a key constraint. Does the problem statement assume a fixed-length pre-allocated array?
loading story #42822005
Sounds promising! What's the key innovation behind it?
loading story #42816281
Cool. This is Lisa and Laura, they are my two retired teachers that are now helping in the library to sort shelves.

Can you explain to them what you want them to now do?

I read the paper and I would like to say, it's confusing at best. But I'm hoping you can help out.

loading story #42815617