sorting with heapsortwe can achieve quicksort' fast running time on almost all inputswith heapsort' ( log nworst-case running time exercise describes this approach the quicksort algorithm is simple to understand and prove correctalthough for many years it had the reputation of being an algorithm that could in theory be highly optimized but in practice was impossible to code correctly like mergesortquicksort is divide-andconquer recursive algorithm let us begin with the following simple sorting algorithm to sort list arbitrarily choose any itemand then form three groupsthose smaller than the chosen itemthose equal to the chosen itemand those larger than the chosen item recursively sort the first and third groupsand then concatenate the three groups the result is guaranteed by the basic principles of recursion to be sorted arrangement of the original list direct implementation of this algorithm is shown in figure and its performance isgenerally speakingquite template void sortvector items ifitems size vector smallervector samevector largerauto chosenitem itemsitems size ]forauto items ifi chosenitem smaller push_backstd::movei )else ifchosenitem larger push_backstd::movei )else same push_backstd::movei )sortsmaller )/recursive callsortlarger )/recursive callstd::movebeginsmaller )endsmaller )beginitems )std::movebeginsame )endsame )beginitems smaller size)std::movebeginlarger )endlarger )enditems larger size)figure simple recursive sorting algorithm