If the array is already sorted on a previous step can we just insert the next element at the right place and remove the previous (FIFO) one?

I believe that would make it O(N) in the worst case instead of O(N*log(N)) as with quick sorting from scratch.

Maybe appending to the sorted array and then sorting it again would be of a similar.

Other ideas - see if could implement something like: http://hdrhistogram.org/
which sacrifices precision for performance