Processes and Threads

Threads are a concept similar to Processes, but with important differences. 

A Simple Threaded Program that Performs a Quicksort on a List of Integers

To begin this discussion, we examined a quicksort program written in Java.  The idea is to have two threads working on separate parts of the data.  There are at least two ways to do this with the quicksort program.

1. Divide the list to be sorted in half. Start one thread to quicksort the first half and a second thread to quicksort the second half.  At the end, the top and bottom halves will be sorted, so they can simply be merged together to obtain a completely sorted list.
2. Run the partition algorithm of quicksort just one time to begin with.  This results in an array in which the first part contains elements that are all less than all elements in the second part.  Then start two threads, one which quicksorts the first part and one that quicksorts the second part.

We use tactic 1 in the code given below.

import java.util.Random;
public class Main
{
    private static int arraySize = 100000;
    private static int [] a = new int [arraySize];
    private static Random randomIntGenerator = new Random(359);

    public static void main(String args[]) throws InterruptedException
   {

       for (int i = 0; i < a.length; i++)
       {
           a[i] = randomIntGenerator.nextInt(1000000);
       }

       int start = (int)System.currentTimeMillis();
       QuicksortThreaded qs1 = new QuicksortThreaded(a, 0, (a.length-1)/2);
       QuicksortThreaded qs2 = new QuicksortThreaded(a, (a.length-1)/2+1, a.length-1);
       Thread qsThread1 = new Thread(qs1);
       Thread qsThread2 = new Thread(qs2);
       qsThread1.start();
       qsThread2.start();
       qsThread1.join();
       qsThread2.join();
       int stop = (int)System.currentTimeMillis();
       int elapsedTime = stop - start;
       System.out.println("Elapsed time: " + elapsedTime);
       // for (int i=0; i < a.length; i++)
       // System.out.println(a[i]);
       // call method merge here to merge the two sorted halves of the array
     }
}

Question

Will the threaded program run faster than a program that does not use threads?

An assignment was given to answer this question.