History of Quicksort

	Revision 13 . . December 19, 2001 12:12 am by AxelBoldt [runtime clarification, slight reformulation of description]
	Revision 12 . . December 18, 2001 4:43 pm by Hannes Hirzel [Added link to external Javascript demo]
	Revision 11 . . October 29, 2001 3:25 pm by Kragen [Added Python implementation of Quicksort.]

---

Difference (from prior major revision) (no other diffs)

Changed: 1c1

Quicksort is a sort algorithm whose [average performance]? is O(n log(n)) and can operate in place. Its inner loop is inherently very fast on nearly all computers, which makes it significantly faster than other O(n lg n) algorithms that can operate in place in the average case. Quicksort's [worst-case performance]? is O(n2): much worse than some other sorting algorithms such as heapsort or merge sort, although careful optimization can make this bad performance very uncommon. Because of its good average performance, Quicksort is one of the most popular sorting algorithms in use. Quicksort was invented by [C. A. R. Hoare]?.

Quicksort is a sort algorithm which, [on average]?, needs O(n log(n)) comparisons to sort n items. It can operate in place, meaning that it does only require a constant amount of additional storage space. Its inner loop is inherently very fast on nearly all computers, which makes it significantly faster than other O(n log n) algorithms that can sort in place in the average case. Quicksort's [worst-case performance]? is O(n2): much worse than some other sorting algorithms such as heapsort or merge sort, although careful optimization can make this bad performance very uncommon. Because of its good average performance and simple implementation, Quicksort is one of the most popular sorting algorithms in use. Quicksort was invented by [C. A. R. Hoare]?.

Changed: 6,7c6,7

divide the list into two sublists, one of all elements greater than the pivot element, and one for all the elements less than the pivot. recursively sort each of the sublists. If one of the sublists is empty, it can be ignored.

reorder the list so that all elements less than the pivot precede all elements greater than the pivot. recursively sort the sublist of elements less than the pivot and the sublist of elements greater than the pivot. If one of the sublists is empty, it can be ignored.