how to sort a queue using (just) another queue and some varibles, in less than O(n^2)?

Question

How can I sort a queue of size N, using just another queue of size N, and a finite number of variables?

the naïve implementation - finding the minimum of the queue and pushing it to the empty queue, then finding the new minimal and pushing it, etc. is O(n^2). is there a more efficient algorithm?

Answer 1

Try Merge Sort, which is O(n log n)