Question

a. Develop a divide-and-conquer algorithm to perform a parallel merge sort of an array. Hint: After division, each process sorts its part of the array using an efficient algorithm. Then, the subarrays are merged into larger sorted subarrays. b. Analyze the communication and computation times if the number of processes is equal to the number of array elements, n. c. Repeat Part b if the number of processes is less than the number of array elements. Assume that the computation time for the sequential sorting algorithm employed is proportional to m log(m), where m is the number of elements being sorted.

Answer 1

import java.util.concurrent.RecursiveAction;

import static io.teivah.mergesort.Utils.merge;

public class ParallelMergeSort extends RecursiveAction {
        private final int[] array;
        private final int[] helper;
        private final int low;
        private final int high;

        public ParallelMergeSort(final int[] array, final int low, final int high) {
                this.array = array;
                helper = new int[array.length];
                this.low = low;
                this.high = high;
        }

        @Override
        protected void compute() {
                if (low < high) {
                        final int middle = (low + high) / 2;
                        final ParallelMergeSort left = new ParallelMergeSort(array, low, middle);
                        final ParallelMergeSort right = new ParallelMergeSort(array, middle + 1, high);
                        invokeAll(left, right);
                        merge(array, helper, low, middle, high);
                }
        }
}