Heap sort will give you n log n.