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( : sorted lists)
:= empty list
while and are both nonempty
  remove smaller of first elements of and from its list; put it at the right end of
 if this removal makes one list empty then remove all elements from the other list and
 append them to
return
{ is the merged list with elements in increasing order}

procedure mergesort()
if then
 
 
 
  merge(mergesort(), mergesort())
{ is now sorted into elements in nondecreasing order}