\documentstyle[11pt,handout]{article}
\begin{document}
\input{localmacros}
\input{macros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\TS}{{\sc Tree-Sort}}
\newcommand{\QS}{{\sc QuickSort}}
\newcommand{\TI}{{\sc Tree-Insert}}
\newcommand{\ITW}{{\sc Inorder-Tree-Walk}}
\newcommand{\ro}{\mbox{{\em root}}}

\head{3390}{Analysis of Algorithms}{21 October 1998}{11}

\begin{center}
\Large{\bf Problem of the Week -- 4}
\end{center}

Given an array $A$ of $n$ distinct numbers, the procedure \TS($A$) sorts $A$
by first building a binary search tree containing the numbers in $A$ and then
printing the numbers in sorted order by an inorder tree walk.
\begin{tabbing}
\TS($A$)\\
1. \= \for\ $i \leftarrow 1$ \myto\ $n$\\
2. \> \= \TI($T$, $A[i]$)\\
3. \> \ITW($\ro(T)$)
\end{tabbing}

In this problem, we establish a surprising similarity between \TS\ and the
running of \QS.  Recall that \QS\ proceeds by repeatedly partitioning elements
around pivot elements.  The running of \QS\ on a given array depends on the
particular choices of the pivot elements around which the partitionings are
performed.  (We saw that if the pivot element is chosen uniformly at random in
each step, then the expected running time is $O(n \lg n)$.)

Consider an implementation of \QS($A$) in which the partitioning of a given
subarray $A[p..q]$ has the following properties: (i) the pivot element is
$A[p]$, i.e., the first element in the subarray, and (ii) in each side of the
partition, the relative order in which the elements appear is the same as the
relative order in which they appear in $A[p..q]$.  Thus, for example,
partitioning the array $[5, 9, 4, 1, 6, 3, 8, 2]$ will lead to the array $[4,
1, 3, 2, 5, 9, 6, 8]$.  Note that (i) the pivot element is the number $5$, and
(ii) in each of the two sides of the partition $[4, 1, 3, 2]$ and $[9, 6, 8]$,
the relative order in which the elements appear is the same as in the original
array.

Prove that the set of comparisons performed in \TS($A$) is {\em exactly} the
set of comparisons performed in the above implementation of \QS($A$).  Hence,
infer that the average-case running time of \TS\ is $O(n \log n)$.
\end{document}