PriorityQueue vs Collections.sort

Question

When would I ever choose Collections.sort() over PriorityQueue, when I know that PQ's would be better in terms of time complexity?

Answer 1

Polling a PriorityQueue for all its elements is effectively heap sorting. Collections.sort() is implemented using merge sorting. Heap sort and merge sort are comparable in terms of time complexity. Both have best case, worst case and average case O(n log n) time complexity.

In terms of performance this is what wikipedia has to say about it:

Heapsort also competes with merge sort, which has the same time bounds. Merge sort requires Ω(n) auxiliary space, but heapsort requires only a constant amount. Heapsort typically runs faster in practice on machines with small or slow data caches. On the other hand, merge sort has several advantages over heapsort:

• Merge sort on arrays has considerably better data cache performance, often outperforming heapsort on modern desktop computers because merge sort frequently accesses contiguous memory locations (good locality of reference); heapsort references are spread throughout the heap.
• Heapsort is not a stable sort; merge sort is stable.
• Merge sort parallelizes well and can achieve close to linear speedup with a trivial implementation; heapsort is not an obvious candidate for a parallel algorithm.
• Merge sort can be adapted to operate on singly linked lists with O(1) extra space. Heapsort can be adapted to operate on doubly linked lists with only O(1) extra space overhead.[citation needed]
• Merge sort is used in external sorting; heapsort is not. Locality of reference is the issue.

PriorityQueue is not meant for sorting, but meant for getting the highest priority element in a changing queue. It also does not improve performance nor does it make your code readable to sort using a PriorityQueue. I would therefore advise you to stick with Collections.sort() when it comes to sorting.

Answer 2

One clear reason you would use Collections.sort() is if you have a List of things to sort already. It can operate directly on that representation (likewise Arrays.sort and an array). Using a PriorityQueue entails copying all the references and computing a heap before you can start polling. And it means copying references into another List data structure.