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.

Leave a Reply

Your email address will not be published. Required fields are marked *