View source for Computer Science/61b/Homework/hw8/GRADER

GRADER file for Homework 8

==Part III==
Running time comparisons – all tests performed on [http://inst.eecs.berkeley.edu/cgi-bin/clients.cgi?choice=13&string= quasar.cs].

 List size  mergesort  quicksort
  10            0          0
  100           3          3
  1,000         42         41
  10,000        120        83
  100,000       665        610
  1,000,000     12928      6947
  10,000,000    273224     130750

==Part IV==
''Is mergesort stable?'' Yes.

''Why or why not?'' When we have two equal keys, we always first insert the key from the left, which came from the left side of the original list. As a result, the key that came from the left stays on the left.

''Is quicksort stable?'' Yes.

''Why or why not?'' We remove keys one by one from left to right. Equivalent keys get inserted in the same order, one by one, into the qEquals queue, which remains untouched after this. When we append qSmall, qEquals, and qLarger, we again work from left to right, and the order is maintained.