4 ms·
Sorting room full of dated reports from several dozens of years. First pass: put raports in the bins year by year maintaining sort order in the bins. Binary se
by stakent 16y ago
Sorting room full of dated reports from several dozens of years.
First pass: put raports in the bins year by year maintaining sort order in the bins. Binary search used to place new report in the bin.
Second pass: put year by year sorted reports in the correct order on the shelfs.
I don't remeber the name of the algorithm used and the book from which it come was given to the library.
- pronoiac 16y agoI'd break the first pass down further, putting items into the (yearly) bins without sorting within each bin, freeing up bins, then subdividing them into smaller piles (say, by month), then sorting those. This insight is courtesy of a sorting algorithm that's optimal for systems with very limited memory but multiple tape systems, if I remember correctly. Also IIRC insertion sort can beat doing the binary sort in situations of 7-20 or so? Much over a dozen, I can't use my fingers of one hand as bookmarks to do, say, three comparisons to find the right place, & I'd rather break it down into more piles.
- allenp 16y agoAlso if you just put them into bins by year, you could have others do the sorting per bin - so more of a distributed model.
- Natsu 16y agoThat's radix sort. For what it's worth, I often have piles of sorted documents to sort together, so I've used merge sort on RL objects fairly regularly. Binary search, too, though I use the optimization where it's not strictly binary when I have a guess about where the item should be. I've probably used a few other algorithms, but I can't think of any off the top of my head.