Is there an existing algorithm for this type of sorting?
This is called bucket sort: split your data range into $k$ "buckets" ($O(k)$), put the data into the buckets ($O(n)$), sort each bucket (however you like), then concatenate all the buckets ($O(k)$). If the sorting is faster than $O(n \log n)$, then the whole algorithm runs faster than any comparison-based sort possibly could!

The problem is that it depends on the distribution of the data. If 99% of your book titles start with A, this gives no real benefit at all! And it doesn't work on data that can't be divided into buckets.

A variation of this, "radix sort", is basically the same except in binary (and with some extra recursion). It runs in $O(wn)$, where $w$ is the bit length of your data (the "word size").