2
$\begingroup$

The quicksort algorithm is based on recursively choosing an element to partition the array. In every modern exposition that I've seen, this element is called the "pivot".

However, as far as I can tell, the inventor of the algorithm used the term "bound" circa 1960, and Robert Sedgewick used the term "partitioning element" in his thesis circa 1980.

So, where did the term "pivot" come from? Was it borrowed from numerical linear algebra (via LU decomposition with pivoting)?

$\endgroup$
1
  • $\begingroup$ Papers from the 60s (Wilkinson (1961), dl.acm.org/doi/pdf/10.1145/321075.321076) already use the word pivot in Gaussian elimination, but I could not find it much earlier. For example it is not used by Goldstine/von Neumann (1947), but seems to be related to Crout's pivotal condensation. $\endgroup$
    – ACL
    Nov 30 '20 at 22:04
4
$\begingroup$

Wegner writes of "pivot element" that partitions the array in Sorting a linked list with equal keys (1982), while none of his references (Sedgewick, Rivest, Loeser, Motzkin) does, as far as I can tell. But it does not pick up until 1986, when multiple authors start using it, including Bing-Chao and Knuth in A one-way, stackless quicksort algorithm. Bentley still does not use it in his Programming Pearls (1986), that introduced Lomuto's version of Quicksort, but The Big White Book (Introduction to Algorithms by Cormen et al., 1990) does.

Wegner gives no reasons for it, or suggests any relation to LU decomposition. But since "pivot elements" partition rows/columns of a matrix in Gaussian elimination and the simplex method (the use dates back to Whittaker (1923)) its appropriation is not particularly surprising, as these things go. "Bound" is the value and not the element, and "partitioning element" is a mouthful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.