How to sort an array of M numbers using N threads in java?

Question

I have to use N(i=1..N) threads to sort an array of M numbers,each thread start to sort the array from position (N*i)%m. Could anyone help me?

Answer 1

What you will want to do is use a divide and conquer sorting method like quick sort.

What you will want to do is partition the array, and then pass the two halves of the array off to another thread to do the processing.

Say you have the number:

11 43 24 56 12 65 90 12 53 23

In one thread, you will partition the numbers:

12 24 11 23 12 | 65 90 53 56 43

Then you can perform quick sort on each half of the array in a different thread.

Allow me to provide some code:

public void multiThreadSort(int threads, int[] arr, int start, int stop) {
    if (threads > 1) {
        int midpoint = partition(arr, start, stop);
        new Thread(){public void run() {
              multiThreadSort(threads - 1, arr, start, midpoint);
        }}.start();
        new Thread(){public void run() {
              multiThreadSort(threads - 1, arr, midpoint, stop);
        }}.start();
    }
    else 
        Arrays.sort(arr, start, stop);
}

public int partition(int[] arr, int start, int stop);

Then call it like so:

multiThreadSort(N, arr, 0, arr.length());

Answer 2

You could let each thread sort its own portion of the array using Arrays.sort(arr, fromIndex, toIndex) and after all threads are done, simply use a merge sort to merge the different results. (Even this step could be parallelized by merging multiple portions at a time.)

Here is a related question / good answer.

Answer 3

Another question is why do you want to do this? Thread creation and destruction is rather heavy, sorting (if you can keep your set in-memory) is rather quick. Doing this make sense only if you have the threads pre-existing in a thread pool for some other reason, if the time to sort M is much greater than the time to create (and probably to destroy) a thread, or if this is an academic exercise to learn about thread manipulation (in which case you shouldn't be asking here). If the time to sort M is greater than the time to create a thread you are probably going to have part of your array in virtual memory and disk paging effects will dominate your performance.

Threads are very useful, even essential, for some algorithms. Sorting is not a good application. Except, as mentioned, as a learning exercise to get experience writing software where your threads play well together.