continuing in this mannerwe obtain ( ( / using log nwe obtain (nnt( log log the choice of which method to use is matter of taste the first method tends to produce scrap work that fits better on standard / sheet of paper leading to fewer mathematical errorsbut it requires certain amount of experience to apply the second method is more of brute-force approach recall that we have assumed the analysis can be refined to handle cases when is not power of the answer turns out to be almost identical (this is usually the casealthough mergesort' running time is ( log )it has the significant problem that merging two sorted lists uses linear extra memory the additional work involved in copying to the temporary array and backthroughout the algorithmslows the sort considerably this copying can be avoided by judiciously switching the roles of and tmparray at alternate levels of the recursion variant of mergesort can also be implemented nonrecursively (exercise the running time of mergesortwhen compared with other ( log nalternativesdepends heavily on the relative costs of comparing elements and moving elements in the array (and the temporary arraythese costs are language dependent for instancein javawhen performing generic sort (using comparator)an element comparison can be expensive (because comparisons might not be easily inlinedand thus the overhead of dynamic dispatch could slow things down)but moving elements is cheap (because they are reference assignmentsrather than copies of large objectsmergesort uses the lowest number of comparisons of all the popular sorting algorithmsand thus is good candidate for general-purpose sorting in java in factit is the algorithm used in the standard java library for generic sorting on the other handin classic ++in generic sortcopying objects can be expensive if the objects are largewhile comparing objects often is relatively cheap because of the ability of the compiler to aggressively perform inline optimization in this scenarioit might be reasonable to have an algorithm use few more comparisonsif we can also use significantly fewer data movements quicksortwhich we discuss in the next sectionachieves this tradeoff and is the sorting routine that has been commonly used in +libraries new ++ move semantics possibly change this dynamicand so it remains to be seen whether quicksort will continue to be the sorting algorithm used in +libraries quicksort as its name implies for ++quicksort has historically been the fastest known generic sorting algorithm in practice its average running time is ( log nit is very fastmainly due to very tight and highly optimized inner loop it has ( worst-case performancebut this can be made exponentially unlikely with little effort by combining quicksort