Computer Science/61b/Homework/hw8/GRADER
< Computer Science | 61b | Homework | hw8
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.
