Sorting and searching at the library

It's my life's dream to do a real-life process vs. algorithm design comparison like this one.

Some day, I will visit hundreds of the world's best kitchens (normalized for ingredients budget) and survey how the instructions filter down from the head chefs there to the prep cooks.

I would love to see the best practices in the process from raw ingredients to completed dishes abstracted to the highest level and then compared with concurrency libraries/best practices to see if there are any places where software design and kitchen instruction exhibit convergent evolution due to pressures they face that are similar on an abstract level.

merge sort bucket sort

1. divide (in half) 1. divide (in bins)

2. sort halves 2. sort bins

3. merge 3. done!

(Edit: Sorry, the formatting isn't great. I don't know how to do fixed-width text.)

The big difference here is that for merge sort, dividing the lists is trivial because all you have to do is split it into the first have and the second half. But for bucket sort, you have to actually look at each element to decide which bin it should go in. This is more like quicksort's partition step.

Librarians aren't as dumb as you make them out to be. Several times I've asked a librarian to locate a mis-shelved book I really needed, and they've always succeeded. I gather it's a pain, but it's considered a big victory.

Also, as a library patron, they've taught me to take any book that I notice mis-shelved and set it on a nearby table.

It never ceases to amaze me how human intelligence and care can transform algorithms that are theoretically brittle into systems than endure for centuries.

This is the fastest sorting algorithm for small arrays, up to maybe 20, 30 elements. Even in software!

No no no. Insertion sort is fastest only when the items being sorted are in nearly sorted order. Its runtime will always be dependent on the number of items, n, being sorted. For a completely randomized array of items, it will run at O(n^2 ) regardless if n is small. Quicksort and Mergesort will do better in these situations.

It's so interesting how we think of cost in a computer vs what really costs us in human time.

The worst of the three jobs was definitely stacking books back on shelves. I'd start with a cart filled with books. OP has it totally right — they are grouped (sometimes, but not always!) by general type — but within those type they're usually randomly arranged.

At this point in time I'd been programming for around a year and a half and was just starting to try to learn about different search algorithms. If only I'd realized that I was sorting every day! Looking back, I found the fastest method (for me) to be quicksort. Go figure!

Or, it could be organized in a circle where you are at the center. You don't move. But you pull/push each book with a magnet. But, RAM is more like the former. So many parallel flip flops. No wonder it's expensive.

I really enjoyed it, it's tricky finding real world metaphors that can be applied and then deconstructed into the technical details, bookmarked to show people struggling to understand algorithms.

At that point, it won't even be necessary to sort.

Once you stop thinking of a library as an array, and be more realistic, you could understand why what the writer is talking about doesn't make much sense.