ParallelMergeSort.java

package org.example;

import java.util.concurrent.RecursiveAction;
import java.util.concurrent.ForkJoinPool;

public class ParallelMergeSort {
    private static final int THRESHOLD = 100;

    private static class MergeSortTask extends RecursiveAction {
        private final Comparable[] array;
        private final Comparable[] tempArray;
        private final int left;
        private final int right;

        public MergeSortTask(Comparable[] array, Comparable[] tempArray, int left, int right) {
            this.array = array;
            this.tempArray = tempArray;
            this.left = left;
            this.right = right;
        }

        @Override
        protected void compute() {
            if (right - left < THRESHOLD) {
                insertionSort(array, left, right);
                return;
            }
            if (left < right) {
                int mid = (left + right) / 2;
                MergeSortTask leftTask = new MergeSortTask(array, tempArray, left, mid);
                MergeSortTask rightTask = new MergeSortTask(array, tempArray, mid + 1, right);
                invokeAll(leftTask, rightTask);
                merge(left, mid, right);
            }
        }

        private void merge(int left, int mid, int right) {
            System.arraycopy(array, left, tempArray, left, right - left + 1);
            int i = left;
            int j = mid + 1;
            int k = left;

            while (i <= mid && j <= right) {
                if (tempArray[i].compareTo(tempArray[j]) <= 0) {
                    array[k++] = tempArray[i++];
                } else {
                    array[k++] = tempArray[j++];
                }
            }

            while (i <= mid) {
                array[k++] = tempArray[i++];
            }

            while (j <= right) {
                array[k++] = tempArray[j++];
            }
        }
    }

    public static void sort(Comparable[] array) {
        Comparable[] tempArray = new Comparable[array.length];
        try (ForkJoinPool pool = new ForkJoinPool()) {
            MergeSortTask task = new MergeSortTask(array, tempArray, 0, array.length - 1);
            pool.invoke(task);
        }
    }

    private static void insertionSort(Comparable[] array, int low, int high) {
        for (int i = low + 1; i <= high; i++) {
            Comparable key = array[i];
            int j = i - 1;
            while (j >= low && array[j].compareTo(key) > 0) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }
}

ParallelQuickSort.java

package org.example;

import java.util.concurrent.RecursiveAction;
import java.util.concurrent.ForkJoinPool;

public class ParallelQuickSort {
    private static final int THRESHOLD = 100;
    private static class QuickSortTask extends RecursiveAction {
        private final Comparable[] array;
        private final int low;
        private final int high;

        public QuickSortTask(Comparable[] array, int low, int high) {
            this.array = array;
            this.low = low;
            this.high = high;
        }

        @Override
        protected void compute() {
            if (high - low < THRESHOLD) {
                insertionSort(array, low, high);
                return;
            }
            if (low < high) {
                int pivotIndex = partition(array, low, high);
                QuickSortTask leftTask = new QuickSortTask(array, low, pivotIndex - 1);
                QuickSortTask rightTask = new QuickSortTask(array, pivotIndex + 1, high);
                invokeAll(leftTask, rightTask);
            }
        }

        private int partition(Comparable[] array, int low, int high) {
            Comparable pivot = array[high];
            int i = low - 1;
            for (int j = low; j < high; j++) {
                if (array[j].compareTo(pivot) <= 0) {
                    i++;
                    swap(array, i, j);
                }
            }
            swap(array, i + 1, high);
            return i + 1;
        }

        private void swap(Comparable[] array, int i, int j) {
            Comparable temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

    public static Comparable[] sort(Comparable[] array) {
        try (ForkJoinPool pool = new ForkJoinPool()) {
            QuickSortTask task = new QuickSortTask(array, 0, array.length - 1);
            pool.invoke(task);
        }
        return array;
    }

    private static void insertionSort(Comparable[] array, int low, int high) {
        for (int i = low + 1; i <= high; i++) {
            Comparable key = array[i];
            int j = i - 1;
            while (j >= low && array[j].compareTo(key) > 0) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }
}