Multithread Quick Sort slower than normal Quick Sort in Java?

Question

Im comparing Quick Sort (normal, with recursivity) and Threaded Quick Sort (Using threads). And i got that Normal-QuickSort is faster than Threaded-QuickSort. Is this right? have a feeling that im doing something wrong.

Here is the code:

public class QuickSort implements SortAlgorithm {
    public void Sort(Integer[] array) {
        Sort(array, 0, array.length-1);
    }

    private void Sort(Integer[] array, Integer low, Integer high) {
        if (low < high) {
            Integer pivot = partition(array, low, high);
            Sort(array, low, pivot-1);
            Sort(array, pivot+1, high);
        }
    }

    private Integer partition(Integer[] array, Integer low, Integer high) {
        Integer pivot = array[high];  
        Integer i = (low-1);
        for (Integer j=low; j<high; j++) 
            if (array[j] < pivot) { 
                i++; 
                Integer temp = array[i]; 
                array[i] = array[j]; 
                array[j] = temp; 
            } 

        Integer temp = array[i+1]; 
        array[i+1] = array[high]; 
        array[high] = temp; 

        return i+1; 
    }
}

public class ThreadsQuickSort extends Thread implements SortAlgorithm {
    private Integer low, high;
    private Integer[] array;

    public ThreadsQuickSort() {
        ;
    }
    
    public ThreadsQuickSort(Integer[] array, Integer low, Integer high) {
        this.array = array;
        this.low = low;
        this.high = high;
    }

    public void run() {
        Sort(array, low, high);
    }

    public void Sort(Integer[] array) {
        Sort(array, 0, array.length - 1);
    }

    private void Sort(Integer[] array, Integer low, Integer high) {
        if (low < high) {
            Integer pivot = partition(array, low, high);
            ThreadsQuickSort lowQSort = new ThreadsQuickSort(array, low, pivot - 1);
            lowQSort.start();
            ThreadsQuickSort highQSort = new ThreadsQuickSort(array, pivot + 1, high);
            highQSort.start();
            try {
                lowQSort.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            try {
                highQSort.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    private Integer partition(Integer[] array, Integer low, Integer high) {
        Integer pivot = array[high];  
        Integer i = (low-1);
        for (Integer j=low; j<high; j++) 
            if (array[j] < pivot) { 
                i++; 
                Integer temp = array[i]; 
                array[i] = array[j]; 
                array[j] = temp; 
            } 

        Integer temp = array[i+1]; 
        array[i+1] = array[high]; 
        array[high] = temp; 

        return i+1; 
    }
}

The main function sorts an array of 10,000 items with both algorithms and get their execution time. Got this output:

Single array sorted in 11 ms
The array was successfully sorted
Threaded array sorted in 6378 ms
The array was successfully sorted

My question is if this is well-coded and the output was expected. This is not about the implementation of Threaded-QuickSort.

You are creating way too many threads. At some point there will be thousands of threads that do nothing but sort two elements, which is extremly inefficient. You are spending more time creating/scheduling/terminating threads than actually sorting the array. You should switch to using a thread pool and rethink how to split your task in parts that are large enough to be executed by a seperate thread each. — akuzminykh
@akuzminykh you are right, but my question is if the output was expected and if i coded something wrong (by example, if my threads are locked or waiting something), it is not about the implementation. — André Kuljis

Surt Surt · Accepted Answer · 2020-11-30T12:16:50

~70 micro creation and switch per thread.

The sum of the threads should be around 20000-1 Which gives 20000 * 70us = 1400000us = 1400ms = 1.4s

So it is nearly the expected.

Multithread Quick Sort slower than normal Quick Sort in Java?

1 Answers