# Merge and mergesort

Head’s up: after Wednesday’s quiz, we’ll use the master theorem to determine a big-O estimate for the complexity of the mergesort algorithm. Today you and your partner implemented the merge algorithm on the ordered sets of numbers that you chose. Merge is a component of mergesort, both described below, so the number of comparisons needed for merge will be part of the function you set up for the master theorem.

procedure merge($L_1, L_2$ : sorted lists)
$L$ := empty list
while $L_1$ and $L_2$ are both nonempty
remove smaller of first elements of $L_1$ and $L_2$ from its list; put it at the right end of $L$
if this removal makes one list empty then remove all elements from the other list and
append them to $L$
return $L$
{$L$ is the merged list with elements in increasing order}

procedure mergesort($L = a_1,\dots, a_n$)
if $n > 1$ then
$m := \lfloor \frac{n}{2} \rfloor$
$L_1 := a_1,a_2,\dots,a_m$
$L_2 := a_{m+1},a_{m+2},\dots,a_n$
$L :=$ merge(mergesort($L_1$), mergesort($L_2$))
{$L$ is now sorted into elements in nondecreasing order}

This entry was posted in Uncategorized. Bookmark the permalink.