Speedsort: improving the quicksort algorithm
Kevin Cleereman · Journal of computing sciences in colleges · 2002
Speedsort is a new sorting algorithm that is based on Quicksort. Like Quicksort, Speedsort uses a pivot value to split an unsorted list into two semi-sorted lists, one of which contains only those elements that are greater than the pivot and one of which contains only those elements that are less than the pivot; because Quicksort and Speedsort utilize swapping instead of merging, they both minimize their space requirements. Unlike Quicksort, the best-case probability for Speedsort is significantly higher than its worst-case probability, causing Speedsort to run 30% faster than Quicksort on average; Quicksort AEs average-case is 1.4*N*log(N), while SpeedsortAEs experimentally determined average-case is 1.0*N*log(N). In addition to its improved runtime, Speedsort is also an improvement over Quicksort in that it is more easily run in parallel or as an external sort routine.