although the implementation we describe in this section for dividing the sequence into two pieces is in-placewe note that the complete quick-sort algorithm needs space for stack proportional to the depth of the recursion treewhich in this case can be as large as admittedlythe expected stack depth is (log )which is small compared to neverthelessa simple trick lets us guarantee the stack size is (log nthe 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 boundarieseach 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 (log nwe leave the details of this implementation as an exercise ( - pivot selection our implementation in this section blindly picks the last element as the pivot at each level of the quick-sort recursion this leaves it susceptible to the th( )-time worst casemost notably when the original sequence is already sortedreverse sortedor nearly sorted as described in section this can be improved upon by using randomly chosen pivot for each partition step in practiceanother common technique for choosing pivot is to use the median of tree valuestaken respectively from the frontmiddleand tail of the array this median-of-three heuristic will more often choose good pivot and computing median of three may require lower overhead than selecting pivot with random number generator for larger data setsthe median of more than three potential pivots might be computed hybrid approaches although quick-sort has very good performance on large data setsit has rather high overhead on relatively small data sets for examplethe process of quicksorting sequence of eight elementsas illustrated in figures through involves considerable bookkeeping in practicea simple algorithm like insertionsort (section will execute faster when sorting such short sequence it is therefore commonin optimized sorting implementationsto use hybrid approachwith divide-and-conquer algorithm used until the size of subsequence falls below some threshold (perhaps elements)insertion-sort can be directly invoked upon portions with length below the threshold we will further discuss such practical considerations in section when comparing the performance of various sorting algorithms