Nitpicking because this tripped me up: You can do this in-place and in O(n) time by repeatedly partitioning the array in half (by value) and discarding the smaller half. I'd have needed a hint that you can do it in one pass to have noticed the summation approach.