chap internal sorting sort routine such as the unix qsort function interestinglyquicksort is hampered by exceedingly poor worst-case performancethus making it inappropriate for certain applications before we get to quicksortconsider for moment the practicality of using binary search tree for sorting you could insert all of the values to be sorted into the bst one by onethen traverse the completed tree using an inorder traversal the output would form sorted list this approach has number of drawbacksincluding the extra space required by bst pointers and the amount of time required to insert nodes into the tree howeverthis method introduces some interesting ideas firstthe root of the bst ( the first node insertedsplits the list into two subliststhe left subtree contains those values in the list less than the root value while the right subtree contains those values in the list greater than or equal to the root value thusthe bst implicitly implements "divide and conquerapproach to sorting the left and right subtrees quicksort implements this concept in much more efficient way quicksort first selects value called the pivot assume that the input array contains values less than the pivot the records are then rearranged in such way that the values less than the pivot are placed in the firstor leftmostk positions in the arrayand the values greater than or equal to the pivot are placed in the lastor rightmostn positions this is called partition of the array the values placed in given partition need not (and typically will notbe sorted with respect to each other all that is required is that all values end up in the correct partition the pivot value itself is placed in position quicksort then proceeds to sort the resulting subarrays now on either side of the pivotone of size and the other of size how are these values sortedbecause quicksort is such good algorithmusing quicksort on the subarrays would be appropriate unlike some of the sorts that we have seen earlier in this quicksort might not seem very "naturalin that it is not an approach that person is likely to use to sort real objects but it should not be too surprising that really efficient sort for huge numbers of abstract objects on computer would be rather different from our experiences with sorting relatively few physical objects the java code for quicksort is as follows parameters and define the left and right indicesrespectivelyfor the subarray being sorted the initial call to quicksort would be qsort(array -