A few years later I learned about sorting algorithms. It's interesting to me that my natural book-sorting intuition was O(n^2) selection sort, but then it wasn't a very big leap for me to tweak it a bit and discover a form of O(n)(ish) radix sort.
In school you don't really spend a few hours manually executing sorting algorithms to build an intuition, so the algorithms can feel a bit like artifacts handed down from the gods. How could someone have come up with these? But then, if that's the specific problem you're trying to solve, developing a fairly efficient and sophisticated (and sometimes opaque to future students) algorithm can feel completely natural.
The concepts don't directly apply to sorting physical books on a shelf. For example, insertion sort works well (pick up any book, then put it in the correct place). It is O(n^2) as implemented as a standard sorting algorithm, shuffling numbers around in an inflexible array. But bookshelves are nothing like that. On the shelf, you just shove everything to the left (or right) in a single operation, opening the gap you need. This is not O(n^2). The bookshelf is more like a doubly linked list than like an array.
This is something of a grandiose claim. How are you thinking of a physical insertion sort working? If you don't have a model, you can't say anything about the time requirements.
But note that if we conceptualize insertion sort like this:
loop:
pick up a book
find the place within the sorted books where this book belongs
open a space for the book
insert the book
The reason insertion sort is O(n^2) when operating on an array is that step 3, "open a space for the book in our hand" is O(n) in that case, because we can only move one book at a time.
I only replied originally because I thought you misread the original comment.
The point of my comment was just that the complexity of an algorithm as analyzed under one set of primitive operations doesn't automatically translate into another set of operations, even when at a high level it's the same algorithm. It is dangerous to study CS, learn that selection sort (on arrays, on a computer well described by a C-like language) is O(n^2), and then conclude that selection sort (in any context) is inherently O(n^2). That may be true of selection sort in specific -- it's difficult to avoid concluding that the selection step is roughly ϴ(n), and must always run n times -- but the reasoning is faulty, and won't transfer to other algorithms.
> GP's description is selection sort, not insertion sort, which still requires
The double-comma construction is meant to be read as an aside. Probably would've been clearer using parens:
> GP's description is selection sort (not insertion sort), which still requires
I often use the commas though because I'm mentally verbalizing what I type and commas have a pause that makes the aside work even aloud, while it's not clear how you'd verbalize parens.
But, while we're here... Insertion sort is O(n^2) on the number of comparison operations, because this step is O(n) on the number of sorted items (you start with 0 of them, and end with n of them, for an average of n/2, which is O(n)):
> find the place within the sorted books where this book belongs
You do this once for each unsorted item (you start with n of them, and end with 0 of them, for an average of n/2, which is O(n)).
Granted, in real life, your brain does a better job of remembering roughly the correct place for each book, so I would say average case with a small number of books you are correct. If you're sorting a large number of books, you need to find the correct spot in less than O(n) comparisons to do better than O(n^2) on the algorithm. I think finding the correct spot would still be O(n), just with a small constant.
Interestingly, if you were sorting a massive volume of books like this and you started to forget the right spot for things, you might modify your strategy and start binary searching for it. This would help you find the spot in O(log(n)), and you'd be doing the sort in O(n*log(n))! It's a small improvement that yields binary insertion sort.
Locating the correct position in the sorted items is O(log n) on the number of sorted items. You point this out yourself later in your comment. Because the sorted items are sorted, it's not necessary to examine each of them.
Doing O(log i) work as i varies from 1 to n is O(log n!) work, which is O(n log n); not much different from doing O(log n) work as i varies from 1 to n.
I'm not sure how to interpret the two halves of this quote. It looks to me like I'm doing O(n log n) comparisons, and also finishing the sort in O(n log n) work overall. I'm not taking O(n^2 log n log n) work to finish the sort.
This is true, but I'm being pedantic and calling the quadratic form of insertion sort just "insertion sort", and the form that does a binary search on the sorted items "binary insertion sort".
It's kind of crazy how often the correct answer in engineering is something like "Eh, N is less than 100,000 and this only runs once. Brute force"
Too often, in my experience, that assumption is made when it is actually technical debt that someone has to pay off down the road. It smells of move fast and break things.
Later when I took courses about RDBMS internals etc it felt like this experience helped a lot.