2

I have implemented a merge sort and would like to run it concurrently. Merge sort works as follows:

i. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element
is considered sorted).

ii. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

The split function is provided below,

 public void mergeSort(int[] arr) {

    if (arr.length <= 1) {
        return;
    }

    int mid = arr.length / 2;

    int[] leftSubArray = Arrays.copyOfRange(arr, 0, mid);
    int[] rightSubArray = Arrays.copyOfRange(arr, mid, arr.length);

    mergeSort(leftSubArray);
    mergeSort(rightSubArray);

    merge(arr, leftSubArray, rightSubArray);
}

The method for the merge is provided,

       private void merge(int[] arr, int[] left_subArray, int[] right_subArray) {

    int i = 0, j = 0;
    int index = 0;

    while ((i < left_subArray.length) && (j < right_subArray.length)) {

        if (left_subArray[i] <= right_subArray[j]) {
            arr[index++] = left_subArray[i++];
        } else {
            arr[index++] = right_subArray[j++];
        }
    }

    while (i < left_subArray.length) {
        arr[index++] = left_subArray[i++];
    }

    while (j < right_subArray.length) {
        arr[index++] = right_subArray[j++];
    }
}

The program is working fine and I thought it might work more efficiently is run concurrently. The code is here,

   public void concurrMergeSort(int[] arr, int numOfThreads) {

        if (numOfThreads <= 1) {
            mergeSort(nums);
            return;
        }

        /*
            split the array in left and right parts
         */
        int middleIndex = arr.length / 2;

        int[] leftArray = Arrays.copyOfRange(arr, 0, middleIndex);
        int[] rightArray = Arrays.copyOfRange(arr, middleIndex, arr.length);

        Thread left = mergeSortThread(leftArray, numOfThreads);
        Thread right = mergeSortThread(rightArray, numOfThreads);

        left.start();
        right.start();

        try {
            left.join();
            right.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        merge(arr, leftArray, rightArray);
    }

    private Thread mergeSortThread(int[] arr, int numOfThreads) {

        return new Thread() {
            @Override
            public void run() {
                // split the thread by half 
                concurrMergeSort(arr, numOfThreads / 2);
            }
        };
    }

Is the implementation is correct?

Arefe
  • 11,321
  • 18
  • 114
  • 168
  • 1
    Do you have reason to think it might not be? – shmosel Apr 03 '18 at 01:02
  • @shmosel look, I have brief experience with concurrency and never need to do the work (I do trading). I expected the computation time should be lesser as I use multithreading but seems the opposite. So may be something needs to be changed? – Arefe Apr 03 '18 at 01:05
  • 1
    Multithreading is a tradeoff. The overhead involved could cost more than it saves at a small scale. Also how are you benchmarking it? – shmosel Apr 03 '18 at 01:07
  • Ok, I use the largest possible array with `int []` :) This is not small scale – Arefe Apr 03 '18 at 01:08
  • I compute the time and so the benchmarking – Arefe Apr 03 '18 at 01:08
  • 1
    Please see [How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) Also, if you're seeing unexpected results (whether in timing or in output), that should be included in the question. – shmosel Apr 03 '18 at 01:10
  • 1
    First required change: change `mergeSort(num);` to `mergeSort(arr);` to make your code compile. – Erwin Bolwidt Apr 03 '18 at 01:29
  • @ErwinBolwidt ok thats a mistake – Arefe Apr 03 '18 at 06:17

0 Answers0