You wrote: > without extra memory, and in guaranteed O(log N)? It seems you meant O(N log N)
You wrote:
It seems you meant O(N log N)