Build a max-heap in the array, then swap the largest value to the end and sift down, again and again. O(n log n) in every case, in place.
This interactive visualization needs JavaScript.