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

Question

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 Java-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?

Answer 1

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