Close Menu
Best in TechnologyBest in Technology
  • News
  • Phones
  • Laptops
  • Gadgets
  • Gaming
  • AI
  • Tips
  • More
    • Web Stories
    • Global
    • Press Release

Subscribe to Updates

Get the latest tech news and updates directly to your inbox.

What's On

Save up to $40 on Our Favorite Buy-It-for-Life Coffee Maker

15 September 2025

Metal Eden Review – Shooting Through The Noise

15 September 2025

USA Today Enters Its Gen AI Era With a Chatbot

15 September 2025
Facebook X (Twitter) Instagram
Just In
  • Save up to $40 on Our Favorite Buy-It-for-Life Coffee Maker
  • Metal Eden Review – Shooting Through The Noise
  • USA Today Enters Its Gen AI Era With a Chatbot
  • Heroes of The Borderlands Impressions – Dungeons & Dragons Has Never Been More Accessible
  • You Can Grab These Deconstructed Old-School Gadget Art Pieces at a Discount Right Now
  • Russia Tests Hypersonic Missile at NATO’s Doorstep—and Shares the Video
  • LEGO Voyagers Review – Studdy Buddies
  • Hundreds of Google AI Workers Were Fired Amid Fight Over Working Conditions
Facebook X (Twitter) Instagram Pinterest Vimeo
Best in TechnologyBest in Technology
  • News
  • Phones
  • Laptops
  • Gadgets
  • Gaming
  • AI
  • Tips
  • More
    • Web Stories
    • Global
    • Press Release
Subscribe
Best in TechnologyBest in Technology
Home » This New Algorithm for Sorting Books or Files Is Close to Perfection
News

This New Algorithm for Sorting Books or Files Is Close to Perfection

News RoomBy News Room16 February 20254 Mins Read
Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
Share
Facebook Twitter LinkedIn Pinterest Email

The original version of this story appeared in Quanta Magazine.

Computer scientists often deal with abstract problems that are hard to comprehend, but an exciting new algorithm matters to anyone who owns books and at least one shelf. The algorithm addresses something called the library sorting problem (more formally, the “list labeling” problem). The challenge is to devise a strategy for organizing books in some kind of sorted order—alphabetically, for instance—that minimizes how long it takes to place a new book on the shelf.

Imagine, for example, that you keep your books clumped together, leaving empty space on the far right of the shelf. Then, if you add a book by Isabel Allende to your collection, you might have to move every book on the shelf to make room for it. That would be a time-consuming operation. And if you then get a book by Douglas Adams, you’ll have to do it all over again. A better arrangement would leave unoccupied spaces distributed throughout the shelf—but how, exactly, should they be distributed?

This problem was introduced in a 1981 paper, and it goes beyond simply providing librarians with organizational guidance. That’s because the problem also applies to the arrangement of files on hard drives and in databases, where the items to be arranged could number in the billions. An inefficient system means significant wait times and major computational expense. Researchers have invented some efficient methods for storing items, but they’ve long wanted to determine the best possible way.

Last year, in a study that was presented at the Foundations of Computer Science conference in Chicago, a team of seven researchers described a way to organize items that comes tantalizingly close to the theoretical ideal. The new approach combines a little knowledge of the bookshelf’s past contents with the surprising power of randomness.

“It’s a very important problem,” said Seth Pettie, a computer scientist at the University of Michigan, because many of the data structures we rely upon today store information sequentially. He called the new work “extremely inspired [and] easily one of my top three favorite papers of the year.”

Narrowing Bounds

So how does one measure a well-sorted bookshelf? A common way is to see how long it takes to insert an individual item. Naturally, that depends on how many items there are in the first place, a value typically denoted by n. In the Isabel Allende example, when all the books have to move to accommodate a new one, the time it takes is proportional to n. The bigger the n, the longer it takes. That makes this an “upper bound” to the problem: It will never take longer than a time proportional to n to add one book to the shelf.

The authors of the 1981 paper that ushered in this problem wanted to know if it was possible to design an algorithm with an average insertion time much less than n. And indeed, they proved that one could do better. They created an algorithm that was guaranteed to achieve an average insertion time proportional to (log n)2. This algorithm had two properties: It was “deterministic,” meaning that its decisions did not depend on any randomness, and it was also “smooth,” meaning that the books must be spread evenly within subsections of the shelf where insertions (or deletions) are made. The authors left open the question of whether the upper bound could be improved even further. For over four decades, no one managed to do so.

However, the intervening years did see improvements to the lower bound. While the upper bound specifies the maximum possible time needed to insert a book, the lower bound gives the fastest possible insertion time. To find a definitive solution to a problem, researchers strive to narrow the gap between the upper and lower bounds, ideally until they coincide. When that happens, the algorithm is deemed optimal—inexorably bounded from above and below, leaving no room for further refinement.

Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
Previous ArticleHiFi audio could finally land on Spotify with a top-up scheme in 2025
Next Article The ‘A Court of Thorns and Roses’ Hulu series is officially dead

Related Articles

News

Save up to $40 on Our Favorite Buy-It-for-Life Coffee Maker

15 September 2025
News

USA Today Enters Its Gen AI Era With a Chatbot

15 September 2025
News

You Can Grab These Deconstructed Old-School Gadget Art Pieces at a Discount Right Now

15 September 2025
News

Russia Tests Hypersonic Missile at NATO’s Doorstep—and Shares the Video

15 September 2025
News

Hundreds of Google AI Workers Were Fired Amid Fight Over Working Conditions

15 September 2025
News

MAHA Wants Action on Pesticides. It’s Not Going to Get It From Trump’s Corporate-Friendly EPA

15 September 2025
Demo
Top Articles

ChatGPT o1 vs. o1-mini vs. 4o: Which should you use?

15 December 2024105 Views

Costco partners with Electric Era to bring back EV charging in the U.S.

28 October 202495 Views

5 laptops to buy instead of the M4 MacBook Pro

17 November 202492 Views

Subscribe to Updates

Get the latest tech news and updates directly to your inbox.

Latest News
News

Russia Tests Hypersonic Missile at NATO’s Doorstep—and Shares the Video

News Room15 September 2025
Gaming

LEGO Voyagers Review – Studdy Buddies

News Room15 September 2025
News

Hundreds of Google AI Workers Were Fired Amid Fight Over Working Conditions

News Room15 September 2025
Most Popular

The Spectacular Burnout of a Solar Panel Salesman

13 January 2025129 Views

ChatGPT o1 vs. o1-mini vs. 4o: Which should you use?

15 December 2024105 Views

Costco partners with Electric Era to bring back EV charging in the U.S.

28 October 202495 Views
Our Picks

Heroes of The Borderlands Impressions – Dungeons & Dragons Has Never Been More Accessible

15 September 2025

You Can Grab These Deconstructed Old-School Gadget Art Pieces at a Discount Right Now

15 September 2025

Russia Tests Hypersonic Missile at NATO’s Doorstep—and Shares the Video

15 September 2025

Subscribe to Updates

Get the latest tech news and updates directly to your inbox.

Facebook X (Twitter) Instagram Pinterest
  • Privacy Policy
  • Terms of use
  • Advertise
  • Contact Us
© 2025 Best in Technology. All Rights Reserved.

Type above and press Enter to search. Press Esc to cancel.