Java Thread CPU usage

Question

I am currently trying to write a quick sort algorithm in Java with usage of threads. But a CPU utilization is never 100%, no matter the length of an array. Can you please help me to find out the problem? Here is my code:

import java.util.Random;

public class Main {

    public static void main(String[] args) {
        int[] arr;
        Random random = new Random();
        arr = new int[53000000];
        for (int i = 0; i < arr.length; i++){
            arr[i] = random.nextInt();
        }
        SortThread sortThread = new SortThread(arr, 0, arr.length - 1);
        Thread threadSort = new Thread(sortThread);
        threadSort.start();
    }

}
public class SortThread implements Runnable {

    private int[] arr;
    private int start;
    private int end;

    public SortThread(int[] arr, int start, int end) {
        this.arr = arr;
        this.start = start;
        this.end = end;
    }

    @Override
    public void run() {

        if (start < end){
            int partitionIndex = partition(arr, start, end);
            SortThread sortThreadLeft = new SortThread(arr, start, partitionIndex - 1);
            SortThread sortThreadRight = new SortThread(arr, partitionIndex + 1, end);
            Thread sortLeft = new Thread(sortThreadLeft);
            Thread sortRight = new Thread(sortThreadRight);
            sortLeft.start();
            sortRight.start();
        }
    }

    private int partition(int arr[], int begin, int end){

        int pivot = arr[end];
        int i = (begin - 1);

        for (int j = begin; j < end; j++){
            if (arr[j] <= pivot ){
                i++;
                int swpTemp = arr[i];
                arr[i] = arr[j];
                arr[j] = swpTemp;
            }
        }

        int swapTemp = arr[i + 1];
        arr[i + 1] = arr[end];
        arr[end] = swapTemp;
        return i + 1;
    }
}

In the Main class I define the array with random elements. In the SortThread class I sort the array using quick sort algorithm. Each sub array is sorted separately in different threads. In a theory this should occupy all the processing power of each CPU. But in practice only 40% is used, no matter the length of an array.

user_11951046 · Answer

How I solved:

import java.util.concurrent.Executors;
import java.util.concurrent.ThreadPoolExecutor;

public class Main {

    static long start;

    public static void main(String[] args) {
        int numOfThreads = 8;
        try {
            numOfThreads = Integer.parseInt(args[0]);
            System.out.println("Number of threads: " + numOfThreads);
        } catch (Exception e) {
            System.out.println("Invalid number of threads: Default 8");
        }

        SortThread.executor = (ThreadPoolExecutor) Executors.newFixedThreadPool(numOfThreads);

        int[] arr = new int[Integer.parseInt(args[1])];
        for (int i = 0; i < arr.length; i++){
            arr[i] = (int)(Math.random() * 256) + 1;
        }

        SortThread sortThread = new SortThread(arr, 0, arr.length - 1);
        Thread threadSort = new Thread(sortThread);
        start = System.nanoTime();
        threadSort.start();
    }

}

class SortThread implements Runnable {
    static ThreadPoolExecutor executor;

    private int[] arr;
    private int start;
    private int end;

    public SortThread(int[] arr, int start, int end) {

        this.arr = arr;
        this.start = start;
        this.end = end;

    }

    @Override
    public void run() {

        if (start < end){
            int partitionIndex = partition(arr, start, end);

            SortThread sortThreadLeft = new SortThread(arr, start, partitionIndex - 1);
            SortThread sortThreadRight = new SortThread(arr, partitionIndex + 1, end);

            Thread sortLeft = new Thread(sortThreadLeft);
            Thread sortRight = new Thread(sortThreadRight);

            SortThread.executor.execute(sortLeft);
            SortThread.executor.execute(sortRight);
        } else {
            if (SortThread.executor.getQueue().size() == 0 && SortThread.executor.getActiveCount() == 1) {
                System.out.println((System.nanoTime() - Main.start)/1000000);
                SortThread.executor.shutdown();
            }
        }
    }

    private static int partition(int[] arr, int begin, int end){

        int pivot = arr[end];
        int i = (begin - 1);

        for (int j = begin; j < end; j++){
            if (arr[j] <= pivot ){

                i++;
                int swpTemp = arr[i];
                arr[i] = arr[j];
                arr[j] = swpTemp;

            }
        }

        int swapTemp = arr[i + 1];
        arr[i + 1] = arr[end];
        arr[end] = swapTemp;

        return i + 1;
    }
}

Just created executor and added all of them to the pool.

Java Thread CPU usage

1 Answers