section we note that we need space for stack proportional to the depth of the recursion treewhich in this case can be as large as admittedlythe expected stack depth is (logn)which is small compared to neverthelessa simple trick lets us guarantee the stack size is (lognthe main idea is to design nonrecursive version of in-place quick-sort using an explicit stack to iteratively process subproblems (each of which can be represented with pair of indices marking subarray boundaries each iteration involves popping the top subproblemsplitting it in two (if it is big enough)and pushing the two new subproblems the trick is that when pushing the new subproblemswe should first push the larger subproblem and then the smaller one in this waythe sizes of the subproblems will at least double as we go down the stackhencethe stack can have depth at most (lognwe leave the details of this implementation to an exercise ( -