Sorting on non-linear topology
If there are $k$ distinct heights, you can sort in $O(n \log k)$ time using a heap or balanced binary tree.  Even better, you can sort with expected time $O(n + k \log k)$, if you use a hashtable.

This leads to a solution to your problem with the corresponding complexity.