Multithreaded quick-sort

Problem Description:

The problem to be solved is the building of a quick- sort program using recursion. Advantages of this approach to the problem are:

The sorting process is very time-efficient

It can operate in-place, that is, in the original array.

The use of recursion in this algorithm makes the logic quite simple. The array to be sorted is split in two sections, each section is sorted and the sorted sections are put together. The function that divides the array does so by picking one element in the array and using it as a so-called pivot. The array is separated into two portions such that every element in one portion is less than the pivot-element and every element in the other portion is greater than or equal to the pivot-element. The algorithm then calls itself on each portion; this process continues until the portion to be sorted contains 1 or 2 elements. After the second portion has been returned, sorted, the two portions are already in-place, in-order and the result is the entire array, sorted.

The special wrinkle to this lab is that you will use multithreading in an attempt to speed-up the algorithm. If your CPU is hyper-threaded and/or you have a multi-core processor, speedup should be detectable.

The key to doing this is to assign the first array-split to two threads. The thing that will slow everything to a crawl is if you assign every split to two more threads. A large sort would then have hundreds or even thousands of threads and the processing will be dominated by the time necessary to create, destroy, start, stop etc. the threads. Using two threads with two processors should give you a speed increase of 20% or more.

The important point to understand is that when the sort routine Returns to caller, it is returning, except for the first call (from main), to a previous instantiation of itself. You may visualize the calling of the sort function as the automatic creation of a separate copy of the sort function which performs its action, separating the array, calling yet another copy of itself for each half and merging the result, and then returning.

Your exercise will involve creating a main program to create the array, call the sort function and display the sorted results. The array will contain 10000 elements and will be filled with double values from a random number generator. Random doubles may be generated by the repeated calling of the random function from the Java Math library, as follows:

// fill an existing array with random doubles

for (int i = 0; i < 10000; ++i)

{

ArrayToBeSorted[i] = Math.random( );

}

This will fill an array named with 10000 random doubles, values between 0.0 and 0.99999999 (1.0 wont be used).

There is no good reason to display 10,000 numbers since no human would be able to see if an out-of-order situation exists. So the final part of the main program will contain a loop that will compare each element to the one immediately after it in the sorted array and display a message if they are out of order.

Testing:

Testing will consist of a comparison between the quicksort without multithreading and quicksort with multithreading. You can use the following code to time your run, once (or more than once and calculate an average) in standard form, before you add the multithreading modification and the time after modification.

long time1 = System.nanoTime();

// here is the place where you place the code

// or the call to code to be timed.

long elapsed = System.nanoTime() - time1;

The resulting time will be in nanoseconds so divide by 1,000,000 to get milliseconds or by 1,000,000,000 to get seconds.

Since the elements to be sorted are random and the program checks itself for correct sorting, no further testing is necessary. So do not display the 10000 values.