Time complexity of iterative quick sort

Question

I have learnt about recursive quick sort and it takes O(nlogn) for best case and O(n^2) for worst case. But i am trying to find time complexity of iterative quick sort.I know it is O(nlogn) for best case and O(n^2). But i am not to justify it for the best case. I am following this tutorial

https://www.techiedelight.com/iterative-implementation-of-quicksort/

say we have 15 elements such that the pivot index postions will always be in the middle making it ideal best case scenario. But i find it the conditon "while (!stack.empty())" i.e the number of partitions will happen for 6 times which is not close to log(n). How one can justify the time complexity of best case in iterative quick sort is O(nlogn).?

Answer 1

In the first partitioning pass, you split into two partitions. That takes O(n). In the next pass you have two partitions, each of which is of size n/2. It takes O(n/2) to partition each of those. Total time for the second pass is O(n/2 + n/2): O(n). Each pass has more partitions, but the partitions are smaller. In total, you make log(n) passes, each of which requires O(n) total time.

It works exactly the way that the recursive version does. The only difference is that in the iterative version you're managing the stack explicitly rather than depending on the implicit stack in the recursive version.