Different algorithms for longest increasing subsequence The longest increasing subsequence problem has a simple and elegant $O(n \log n)$ time solution via patience sorting.

Such a basic and well-studied problem, however, should have a number of different solutions, just as sorting does.

Are there other distinct $O(n \log n)$ time algorithms for this problem?
There is a $O(n \log \log n)$ time algorithm to solve the longest increasing subsequence problem. You may find this and the paper by Sergei Bespamyatnikh , Michael Segal helpful.