\documentstyle[/fs/www/class/spring2002/cmsc251/bin/HW,11pt]{article}
\thispagestyle{empty}

\begin{document}

\handhead{Runtimes and other results for various comparison-based sorting algorithms}

\begin{tabular}{r|l|l|l|l|}
   & \multicolumn{1}{c|}{Worst Case} & \multicolumn{1}{c|}{Average Case}
	& \multicolumn{1}{c|}{In place} & \multicolumn{1}{c|}{Locality}
	\\ \hline
Insertion Sort & $\frac{n^2}{2}$ & $\frac{n^2}{4}$ & Yes & Yes \\ \hline
Merge Sort$^*$ & $n \lg n$ & $n \lg n$ & No$^{**}$ & Yes \\ \hline
Heap Sort & $2n \lg n$ & $2n \lg n~^{***}$ & Yes & No \\ \hline
Quick Sort & $\frac{n^2}{2}$ & $\sim 1.39 n \lg n$ & Yes & Yes \\ \hline
\end{tabular}

\bigskip

\noindent
$^{*}$For a Merge procedure that always does exactly $n-1$ comparisons\\
on each call with $n$ items.

\smallskip

\noindent
$^{**}$Can be done in place, but not practical.

\smallskip

\noindent
$^{***}$Hard to prove.

\bigskip

\bigskip

The above expressions for runtime give the highest-order terms only,
but with the correct coefficients.

This does not take account of other time-consuming aspects of the
algorithms, especially data movement. But as a general rule in
comparison-based algorithms, there are at most no more data movements
than there are comparisons (since data is generally moved only in
response to a comparison). 

So (assuming that an assignment statement takes no more time than a
comparison) we can multiply the above runtimes by two to get a rough
upper estimate that comes closer to actual behavior in those cases
that do in fact perform many moves.  It happens that on average,
Quicksort performs only about 1/3 as many moves as comparisons, while
the others perform proportionately more.

\end{document}
