Quicksort with a stable partitioning step builds as its recursion tree exactly the search tree you get by inserting the input, left to right. Both processes even execute the same set of key comparisons, only in a different order: Quicksort compares a whole sublist against one pivot at a time (a column of the matrix), the tree compares one element at a time against the nodes on its search path (a row). The correspondence survives equal keys (fat pivot) and median-of-k pivots, where the binary search tree becomes a k-fringe-balanced tree. Hover any element or matrix cell to follow it through both pictures.
.txt files of algs4, e.g. S O R T E X A M P L E). If all keys are numbers they
are compared numerically, otherwise as strings. Duplicates are allowed. At most 30 keys.
k = 5 sets the sample size (odd, 1 to 9); without it, the current
setting is kept. Text after # is a comment.
keys, k, order=q|t, detail=fine|coarse,
speed (ms), lab=res|ord, sort=pos|key, present=1,
text=1. In presentation mode: → / PgDn step, ← / PgUp back, space plays, Esc leaves.
Quicksort (on a sublist with $n$ elements): if $n \le k-1$, stop (the sublist would be left to Insertionsort, whose comparisons we ignore here); otherwise the pivot $P$ is the median of the first $k$ elements of the sublist (for $k=1$: simply the first element). Then every element of the sublist is compared with $P$ and appended to one of three segments, smaller, equal and larger, which keep the original relative order (stable partitioning). The equal segment is done (the fat pivot); Quicksort recurses on smaller, then on larger.
Search tree (insert the input left to right): an insertion compares the new key with the inner nodes on its search path; if it finds its key in an inner node, it stops. Otherwise it reaches a leaf. Leaves are buffers for up to $k-1$ elements (for $k=1$ they are always empty). When the $k$th element arrives, the leaf is split: the buffer partitions itself around the median of its $k$ elements, which pops out as a new inner node; the smaller and larger elements become its two new leaves, duplicates of the median are dropped. For $k=1$ this is the ordinary binary search tree; for $k\ge3$ it is a $k$-fringe-balanced tree.
That both give the same tree and the same comparisons rests on the stable partitioning: the elements reaching a subtree arrive there in the same relative order in both processes, so the first $k$ elements of a sublist are exactly the first $k$ elements that land in the corresponding leaf. (With an in-place, non-stable partitioning method the correspondence only holds in distribution for random inputs.)
Counting. The pivot is never compared with itself: partitioning a sublist of $n$ elements costs $n-1$ comparisons, and in the tree, an element is compared with the inner nodes on its path; the element that becomes a new node is not compared with it (for $k=1$, the first insertion of a key creates its node without any comparison). Duplicates of a pivot are compared with it ($=$), in both processes. So no comparison lies on the diagonal of the matrices. Finding the median of the sample is not counted (in either process). With this convention, for $k=1$ and a random permutation of distinct keys, both processes satisfy \[ C_n \wrel= n - 1 + \frac1n \sum_{r=1}^{n} \bigl(C_{r-1} + C_{n-r}\bigr) \wrel= n - 1 + \frac2n\sum_{j=0}^{n-1} C_j, \qquad C_0 \wrel= 0 . \] Counting element visits instead (each element of a sublist, the pivot included), adds exactly one per inner node to both processes. Likewise, searching each input element in the final tree costs one more comparison per inner node than building it (the diagonal).
Further reading: the correspondence for equal keys and pivot sampling, and its use for the analysis of Quicksort, is worked out in Quicksort Is Optimal for Many Equal Keys (Section 2 and Lemma 6.1).