Homework 4

Details

Finish optimizing either Quicksort or Mergesort. Grades for this assignment will be based mainly on performance improvements compared to the original algorithm. I will also compare your performance with that of qsort, your classmates, and (if I get around to it) my best algorithms.

To get an 'A', you want to be the fastest algorithm. To get a 'B', you want to have made significant improvements and it should be obvious that you put effort into the improvements. (For instance, your attempts should not be limited to changing just 2 or 3 lines of code and/or implementing just one improvement.)

If you choose mergesort, you will likely not beat the best versions of quicksort. However, if you make significant enough improvements to it, that will be considered good enough (since you are limited by the algorithm). Hint: There is an improvement that can make it about twice as fast by reducing the amount of copying of arrays that is done.

Zip up the Sorting directory and submit it using handin. You can use the 385SRQ assignment.