chap internal sorting simple improvement might then be to replace quicksort with faster sort for small numberssay insertion sort or selection sort howeverthere is an even better -and still simpler -optimization when quicksort partitions are below certain sizedo nothingthe values within that partition will be out of order howeverwe do know that all values in the array to the left of the partition are smaller than all values in the partition all values in the array to the right of the partition are greater than all values in the partition thuseven if quicksort only gets the values to "nearlythe right locationsthe array will be close to sorted this is an ideal situation in which to take advantage of the best-case performance of insertion sort the final step is single call to insertion sort to process the entire arrayputting the elements into final sorted order empirical testing shows that the subarrays should be left unordered whenever they get down to nine or fewer elements the last speedup to be considered reduces the cost of making recursive calls quicksort is inherently recursivebecause each quicksort operation must sort two sublists thusthere is no simple way to turn quicksort into an iterative algorithm howeverquicksort can be implemented using stack to imitate recursionas the amount of information that must be stored is small we need not store copies of subarrayonly the subarray bounds furthermorethe stack depth can be kept small if care is taken on the order in which quicksort' recursive calls are executed we can also place the code for findpivot and partition inline to eliminate the remaining function calls note however that by not processing sublists of size nine or less as suggested aboveabout three quarters of the function calls will already have been eliminated thuseliminating the remaining function calls will yield only modest speedup heapsort our discussion of quicksort began by considering the practicality of using binary search tree for sorting the bst requires more space than the other sorting methods and will be slower than quicksort or mergesort due to the relative expense of inserting values into the tree there is also the possibility that the bst might be unbalancedleading to th( worst-case running time subtree balance in the bst is closely related to quicksort' partition step quicksort' pivot serves roughly the same purpose as the bst root value in that the left partition (subtreestores values less than the pivot (rootvaluewhile the right partition (subtreestores values greater than or equal to the pivot (roota good sorting algorithm can be devised based on tree structure more suited to the purpose in particularwe would like the tree to be balancedspace efficient