I was asked to sort a doubly linked list in log(n) time complexity. I was able to provide the brute force O(n^2) and a optimized on in O(NlogN) using merge sort. But was unable to get the log(n) solution. The interviewer was not expecting anything less than log(n) and told me I failed. Does anyone know the solution of the above problem.

He gave a hint to use a TreeNode but I was unable get to the solution.