Can be done with Patience sort


#1

This problem can be solved in O(log n ) time and o(n) space using patience sort


#2

It must be O(nlogn) instead.