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