There are certain algorithms whose running time can decrease significantly when one divides up a task and gets each part done in parallel. One of these algorithms is merge sort, where a list is divided into infinitesimally smaller parts and then recombined in a sorted order. I decided to do an experiment to test whether or not I could I increase the speed of this sort by using multiple threads. I am running the following functions in Java on a Quad-Core Dell with Windows Vista.

One function (the control case) is simply recursive:

// x is an array of N elements in random order
public int[] mergeSort(int[] x) {
    if (x.length == 1) 
        return x;

    // Dividing the array in half
    int[] a = new int[x.length/2];
    int[] b = new int[x.length/2+((x.length%2 == 1)?1:0)];
    for(int i = 0; i < x.length/2; i++) 
        a[i] = x[i];
    for(int i = 0; i < x.length/2+((x.length%2 == 1)?1:0); i++) 
        b[i] = x[i+x.length/2];

    // Sending them off to continue being divided
    mergeSort(a);
    mergeSort(b);

    // Recombining the two arrays
    int ia = 0, ib = 0, i = 0;
    while(ia != a.length || ib != b.length) {
        if (ia == a.length) {
            x[i] = b[ib];
            ib++;
        }
        else if (ib == b.length) {
            x[i] = a[ia];
            ia++;
        }
        else if (a[ia] < b[ib]) {
            x[i] = a[ia];
            ia++;
        }
        else {
            x[i] = b[ib];
            ib++;
        }
        i++;
    }

    return x;
}

The other is in the 'run' function of a class that extends thread, and recursively creates two new threads each time it is called:

public class Merger extends Thread
{
    int[] x;
    boolean finished;

    public Merger(int[] x)
    {
        this.x = x;
    }

    public void run()
    {
        if (x.length == 1) {
            finished = true;
            return;
        }

        // Divide the array in half
        int[] a = new int[x.length/2];
        int[] b = new int[x.length/2+((x.length%2 == 1)?1:0)];
        for(int i = 0; i < x.length/2; i++) 
            a[i] = x[i];
        for(int i = 0; i < x.length/2+((x.length%2 == 1)?1:0); i++) 
            b[i] = x[i+x.length/2];

        // Begin two threads to continue to divide the array
        Merger ma = new Merger(a);
        ma.run();
        Merger mb = new Merger(b);
        mb.run();

        // Wait for the two other threads to finish 
        while(!ma.finished || !mb.finished) ;

        // Recombine the two arrays
        int ia = 0, ib = 0, i = 0;
        while(ia != a.length || ib != b.length) {
            if (ia == a.length) {
                x[i] = b[ib];
                ib++;
            }
            else if (ib == b.length) {
                x[i] = a[ia];
                ia++;
            }
            else if (a[ia] < b[ib]) {
                x[i] = a[ia];
                ia++;
            }
            else {
                x[i] = b[ib];
                ib++;
            }
            i++;
        }

        finished = true;
    }
}

It turns out that function that does not use multithreading actually runs faster. Why? Does the operating system and the java virtual machine not "communicate" effectively enough to place the different threads on different cores? Or am I missing something obvious?