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

\head{3390}{Analysis of Algorithms}{Spring 1999}{7 April 1999}{8}

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

\bigskip
Consider a scenario where we need to sort a list of $n$ records, in which the
number $m$ of distinct keys is much less than $n$.  This scenario may arise,
for example, in bulk mailing when we may wish to sort a large mailing list by
zip codes.  Of course, one way to sort the list is to use a $\Theta(n \lg
n)$-time sorting algorithm like mergesort.  If $m \ll n$, however, one can do
better.

Design an efficient sorting algorithm to sort a list of $n$ records with $m$
distinct keys.  Your algorithm must asymptotically outperform mergesort when
$m \ll n$.  ({\em Hint:} A worst-case running time of $O(n \lg m)$ is
achievable.)
\end{document}