Why is my threaded sort algorithm slow compared to the non-threaded version?

I just have implemented a threaded version of the merge sort. ThreadedMerge.java: http://pastebin.com/5ZEvU6BV

Since merge sort is a divide and conquer algorithm I create a thread for every half of the array. But the number of avialable threads in J开发者_运维问答ava-VM is limited so I check that before creating threads:

if(num <= nrOfProcessors){
    num += 2;
   //create more threads
}else{
   //continue without threading
}

However the threaded sorting takes about ~ 6000 ms while the non-threaded version is much faster with just ~ 2500 ms.

Non-Threaded: http://pastebin.com/7FdhZ4Fw

Why is the threaded version slower and how do I solve that problem?

Update: I use atomic integer now for thread counting and declared a static field for Runtime.getRuntime().availableProcessors(). The sorting takes about ~ 1400 ms now.

However creating just one thread in the mergeSort method and let the current thread do the rest has no sigificant performance increase. Why?

Besides when after I call join on a thread and after that decrement the number of used threads with

num.set(num.intValue() - 1);

the sorting takes about ~ 200 ms longer. Here is the update of my algorithm http://pastebin.com/NTZq5zQp Why does this line of code make it even worse?

first off your accesses to num is not threadsafe (check http://download.oracle.com/javase/6/docs/api/java/util/concurrent/atomic/AtomicInteger.html )

you create an equal amount of processes to cores but you block half of them with the join call

num += 1;
ThreadedMerge tm1 = new ThreadedMerge(array, startIndex, startIndex + halfLength);
tm1.start();
sortedRightPart = mergeSort(array, startIndex + halfLength, endIndex);
try{
    tm1.join(); 
    num-=1
    sortedLeftPart = tm1.list;
}catch(InterruptedException e){
}

this doesn't block the calling thread but uses it to sort the right part and let the created thread do the other part when that one returns the space it takes up can be used by another thread

Hhm, you should not create a thread for every single step (they are expensive and there are lightweight alternatives.)

Ideally, you should only create 4 threads if there are 4 CPU´s.

So let´s say you have 4 CPU´s, then you create one thread at the first level (now you have 2) and at the second level you also create a new thread. This gives you 4.

The reason why you only create one and not two is that you can use the thread you are currently running like:

Thread t = new Thread(...);
t.start();

// Do half of the job here

t.join(); // Wait for the other half to complete.

If you have, let´s say, 5 CPU´s (not in the power of two) then just create 8 threads.

One simple way to do this in practice, is to create the un-threaded version you already made when you reach the appropriate level. In this way you avoid to clutter the merge method when if-sentences etc.

The call to Runtime.availableProcessors() appears to be taking up a fair amount of extra time. You only need to call it once, so just move it outside of the method and define it as a static, e.g.:

static int nrOfProcessors = Runtime.getRuntime().availableProcessors();