# 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.