This problem can be solved in O(log n ) time and o(n) space using patience sort
It must be O(nlogn) instead.
