Efficient implementations of Quicksort are not a stable sort, meaning that the relative order of equal sort items is not preserved. develop by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a normally used algorithm for sorting. Robert Sedgewick's Ph.D. thesis in 1975 is considered a milestone in the survey of Quicksort where he resolved many open problems associated to the analysis of various pivot choice schemes including Samplesort, adaptive partitioning by Van Emden as well as derivation of expected number of comparisons and swaps. Jon Bentley and Doug McIlroy integrated various improvements for purpose in programming library, including a technique to deal with equal components and a pivot scheme known as pseudomedian of nine, where a sample of nine components is divided into groups of three and then the median of the three medians from three groups is choose. In the Java core library mailing lists, he initiated a discussion claiming his new algorithm to be superior to the runtime library's sorting method, which was at that time based on the widely used and carefully tuned variant of classic Quicksort by Bentley and McIlroy.
Recursively use the above steps to the sub-array of components with smaller values and separately to the sub-array of components with greater values. The pivot choice and partitioning steps can be done in several different ways; the choice of specific implementation schemes greatly affects the algorithm's performance.
""" This is a pure Python implementation of the quick sort algorithm For doctests run following command: python -m doctest -v quick_sort.py or python3 -m doctest -v quick_sort.py For manual testing run: python quick_sort.py """ def quick_sort(collection): """Pure implementation of quick sort algorithm in Python :param collection: some mutable ordered collection with heterogeneous comparable items inside :return: the same collection ordered by ascending Examples: >>> quick_sort([0, 5, 3, 2, 2]) [0, 2, 2, 3, 5] >>> quick_sort()  >>> quick_sort([-2, -5, -45]) [-45, -5, -2] """ length = len(collection) if length <= 1: return collection else: # Use the last element as the first pivot pivot = collection.pop() # Put elements greater than pivot in greater list # Put elements lesser than pivot in lesser list greater, lesser = ,  for element in collection: if element > pivot: greater.append(element) else: lesser.append(element) return quick_sort(lesser) + [pivot] + quick_sort(greater) if __name__ == "__main__": user_input = input("Enter numbers separated by a comma:\n").strip() unsorted = [int(item) for item in user_input.split(",")] print(quick_sort(unsorted))