In reply to sjain12:
The LRM does not specify how a tool should implement a sorting method. But I’ve got to believe any built-in sorting method is going to be faster than what you could write just because of the direct access the tool has to the data. Also, since the queue is in mostly sorted order already, you will be near best case performance anyway for most sort algorithms.
But another factor you should consider is the choice of array type. Queues are very efficient when accessing the head or tail elements, but become very inefficient when accessing the middle elements. You might want to consider using a dynamic array where there is uniform access to every element. Resizing a dynamic array to grow by one element does not usually mean reallocating the entire array as much as you think it would.
You probably should try some experiments with your tool before making a decision.