 Homework 12Details
Note: You may work in teams of 2 on this project if you wish.
But if you do, you must do pairprogramming! In other words, you
must work sidebyside on the coding instead of trying to divideandconquer.
If you plan to implement quicksort, I highly recommend working in pairs.
Implement either Mergesort or Quicksort using the algorithm given in the SIPC notes. Run tests to compare it with an optimized serial version and your naive parallel version from HW 9 (which you are welcome to improve a bit if you wish).
Zip up your Sorting directory and submit it using Web handin as usual.
Here are some resources you might find helpful
 SPAC_CPP.pdf
A version of the Parallelism and Concurrency written for OpenMP instead of Java.
 OpMPSorting My OpenMP version of parallel sum, parallelprefix sum, and a start of the pack and partition algorithms.
Feel free to use as you wish, but give credit!
Use the Download Zip file link to download all of the files.
The zipfile also includes two test cases for the runSorts algorithm
and the results of my algorithm on those test cases.
Submit a hardcopy of a writeup that includes the following.
(Please take the writeup seriously and don't just throw it together at the last minute.)

A chart that compares the performance of the various algorithms. At a minimum, both parallel algorithms should be run on 1, 2, 4, and 8 threads.
If you have access to a machine with more cores, run in on that as well.

Discuss how the algorithms compare with each other. Is the newandimproved algorithm better than your naive one? If not, explain why you think it is the case. Discuss what would happen if you had a lot more processors.

Grade yourself out of 20 points, providing a clear justification.
If you are unable to complete the implementation of quicksort, you may receive up to 13/20 points for a proper implementation of pack and up to 16/20
points for a proper implementation of partition (although if you get partition correct, there is no reason that you shouldn't also get quicksort correct). My code (given above) already has a test program for pack. If you get partition correct but not quicksort, include a program that tests your partition algorithm.
