Multi-threading sorting algorithms

Question

I have to implement a multi threaded Merge Sort and Quick sort in Java for my algorithms class and compare them to my single threaded versions. However, I have never multithreaded before.

Is the code I have able to be multi threaded or do I have to start again?

Here is my code for the single thread algorithms Merge Sort. the sort() method is part of the strategy pattern I have to implement.

    @Override
public int[] sort(int[] list) {
    int array_size = list.length;
    list = msort(list, 0, array_size-1);
    return list;
}

int[] msort(int numbers[], int left, int right) {
    int mid;
    if (left<right) {
        mid = (right + left) / 2;
        msort(numbers, left, mid);
        msort(numbers, mid+1, right);
        merge(numbers, left, mid, mid+1, right);
    }
    return numbers;
}

void merge(int numbers[], int startA, int endA, int startB, int endB) {
    int finalStart = startA;
    int finalEnd = endB;
    int indexC = 0;
    int[] listC = new int[numbers.length];

    while(startA <= endA && startB <= endB){
        if(numbers[startA] < numbers[startB]){
            listC[indexC] = numbers[startA];
            startA = startA+1;
        }
        else{
            listC[indexC] = numbers[startB];
            startB = startB +1;
        }
        indexC++;
    }

    if(startA <= endA){
        for(int i = startA; i < endA; i++){
            listC[indexC]= numbers[i];
            indexC++;
        }
    }

    indexC = 0;
    for(int i = finalStart; i <= finalEnd; i++){
        numbers[i]=listC[indexC];
        indexC++;
    }
}

Here is my quick sort

    @Override
public int[] sort(int[] list) {
    int[] array = quickSort(list, 0, list.length-1);
    return array;
}
int partition(int arr[], int left, int right)
{
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];

      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

      return i;
}

int[] quickSort(int arr[], int left, int right) {
      int index = partition(arr, left, right);
      if (left < index - 1)
            quickSort(arr, left, index - 1);
      if (index < right)
            quickSort(arr, index, right);
      return arr;
}

Cheers!

Answer 1

A major advice in this case (a mistake that I've made when I was in your shoes and I've seen many others do it) is to not let the number of threads grow unchecked. Remember that if you start one thread per recursion branch, the main thread will spawn one child thread (assuming one recursive call is done on the main itself), the child thread will spawn an additional thread and so on until you will choke the system if your data set is large.

A more clear alternative would be to start one thread per recursive call, such that each thread spawns two child threads and then joins them.

Either way, make sure to set a limit on the recursion depth that spawns threads (let's say equal to the number of CPU cores) and if the limit is exceeded, call the sort method sequentially on the rest of the levels.

Answer 2

Short answer - yes, these algorithms can be converted to be multi-threaded without starting from scratch (so far as I can see).

The key elements that make these "easy" to parallelize are:

• There are two recursive calls within each implementation
• Those two recursive calls operate on separate pieces of data - they shouldn't conflict with each other (e.g. even when working inside the same array, they're operating on different indices)
• The method making those recursive calls cannot proceed until both are complete
• That it doesn't matter which order those two calls are made in

That's answered some of your questions, hopefully.

---

Some more advice, not sure how useful this will be:

• If you put both recursive calls into a new thread, then the current thread will be idle while waiting for them both to complete
• When the number of elements left to work on is small, the overheads of threading may be higher than the gains.
• You might want to throttle the number of threads being used for this task in general - you might want to use some form of thread pool or work queue, with a fixed number of threads.