\documentclass[12pt]{article}
\usepackage{graphics,epsfig}

\usepackage{geometry} 

\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}
\newcommand{\myspan}{\mbox{span}}

\begin{document}

\title{CS 141: Advanced Topics in Algorithms \\ Spring 2006 \\ Sorting Networks Homework}
\author{}
\date{Due:  Wednesday, March 3 by 5 PM under Ran's Office Door}
\maketitle

\begin{enumerate}

  \item \Points{10} \Name{Odd-Even Mergesort!}
  Recall the Odd-Even Mergesort algorithm from class.\\
  
  \textsc{Odd-Even Merge:}
  \begin{itemize}
    \item Input: a sequence $a_1a_2\ldots a_n$, where both halves ($a_1a_2\ldots a_{n/2}$
    and $a_{n/2 + 1} a_{n/2+2} \ldots a_n$) are sorted.
    \item Step 1: Recursively merge the even-indexed subsequence $a_2a_4a_6\ldots a_n$.
    \item Step 2: Recursively merge the odd-indexed subsequence $a_1a_3a_5\ldots a_{n-1}$.
    \item Step 3: For all $i \in \{1, 3, 5, \ldots n-3\}$, compare $a_i$ and $a_{i+1}$ with
    a comparator (so the two will be swapped if $a_i > a_{i+1}$).
  \end{itemize}
  
  \textsc{Odd-Even Mergesort}: 
  Given a sequence $a_1a_2\ldots a_n$, recursively sort both halves ($a_1a_2\ldots a_{n/2}$
    and $a_{n/2 + 1} a_{n/2+2} \ldots a_n$). Then merge them using Odd-Even Merge.\\
    
   Prove the correctness of \textsc{Odd-Even Mergesort} and show that its depth is
   $O(\log^2 n)$. You may use without proof the result from class that
   \textsc{Odd-Even Merge} has a depth of $O(\log n)$. 

  
    
\end{enumerate}

\end{document}
