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.
> Insertion sort is O(n^2) on the number of comparison operations, because this step is O(n) on the number of sorted items
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.
> Because the sorted items are sorted, it's not necessary to examine each of them.
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".
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.