Comment by shiandow

Interestingly sorting is O(N) for a surprisingly large class of datatypes. Anything that behaves well with lexicographic sorting really.

Supposing one uses a 'trie' as a priority queue, the inserts and pops are effectively constant.