Quicksort

Download the support code for this lab. Look at the base quicksort implementation (QuickSortBasic class), at the tests offered and at the Main program.

Also download the lecture notes on this subject.

Exercises:

1. Starting from QuickSortBasic, build the task-decomposed version of QuickSort to in slide 17 of the lecture.
2. Starting from QuickSort with Tasks, build the parallel version of QuickSort to in slide 21 of the lecture.
3. Starting from the parallel version of quicksort, build a more efficient parallel version,  where the parallel tasks are created only at the topmost level, and all subsequent recursive calls are performed sequentially.
4. Improve the above version by selecting the median element of the array as pivot.

Note:  To analyze the performance of the parallel algorithm, use an input ArrayList that gets sorted in a few seconds on your machine.