Lesson plan

Quicksort

Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961. It is still a commonly used algorithm for sorting. Overall, it is slightly faster than merge sort and heapsort for randomized data, particularly on larger distributions. Quicksort is a divide-and-conquer algorithm. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting. Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. It is a comparison-based sort since elements a and b are only swapped in case their relative order has been obtained in the transitive closure of prior comparison-outcomes. Most implementations of quicksort are not stable, meaning that the relative order of equal sort items is not preserved. Mathematical analysis of quicksort shows that, on average, the algorithm takes O(n \log{n}) comparisons to sort n items. In the worst case, it makes O(n^2) comparisons.

Back to article

Article summary

Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961. It is still a commonly used algorithm for sorting. Overall, it is slightly faster than merge sort and heapsort for randomized data, particularly on larger distributions. Quicksort is a divide-and-conquer algorithm. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting. Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. It is a comparison-based sort since elements a and b are only swapped in case their relative order has been obtained in the transitive closure of prior comparison-outcomes. Most implementations of quicksort are not stable, meaning that the relative order of equal sort items is not preserved. Mathematical analysis of quicksort shows that, on average, the algorithm takes O(n \log{n}) comparisons to sort n items. In the worst case, it makes O(n^2) comparisons.

Key claims

  1. publication date: 1961 — source: Wikipedia, revision 1377696753, retrieved 2026-10-20 · confidence 0.95
  2. publication date: 1962 — source: Wikipedia, revision 1377696753, retrieved 2026-10-20 · confidence 0.95
  3. publication date: 1961-07-07 — source: Wikipedia, revision 1377696753, retrieved 2026-10-20 · confidence 0.95

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. The record states that the publication date is "1961". What evidence would count against this claim?
  3. The record states that the publication date is "1962". What evidence would count against this claim?
  4. The record states that the publication date is "1961-07-07". What evidence would count against this claim?
  5. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  6. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

  1. Wikipedia, “Quicksort”, revision 1377696753, retrieved 2026-10-20 https://en.wikipedia.org/w/index.php?oldid=1377696753

Key claims and bibliography are generated from the same tracked claims and sources as the article page.