I used it for the median calculation of FASTQ quality scores (https://en.wikipedia.org/wiki/FASTQ_format). But in the end I used the frequency table to calculate the median more quickly. So as you say, the frequency table turned out to be more useful.

Having said that the usefulness depends on how many times 8-bit data is passed into sorted. (bytes,bytearrays, most python strings are 8-bit I believe). I raised this issue not because I want a .sort() method on bytes or 
bytearrays, but mostly because I think python's sorted function can be improved with regards to 8-bit data. I think it is an interesting thing to consider, depending on how often this occurs.

For example:
sorted(b'Let\'s test a proper string now. One that has some value to be sorted.')
and 
list(bytes_sort(b'Let\'s test a proper string now. One that has some value to be sorted.'))

This returns the same result (a list of integers). But the byte_sort implementation is 2.5 times faster. So sorted is not optimally implemented here.

Since sorted is now basically throwing everything into list.sort an alternative codepath using bytes.sort can be considered. (If there are enough use cases for it).