Computer Science/61b/Homework/hw8/GRADER

GRADER file for Homework 8

Part III

Running time comparisons – all tests performed on 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.