归并排序的并发计算实现咨询：已实现归并排序，如何使其并发运行？

嘿，很高兴帮你把归并排序改成并发版本！归并排序天生就适合并行化，因为它的拆分阶段完全是独立的——左右子数组的排序互相不依赖，刚好可以丢给不同线程去跑。下面我给你两种常见的实现方式，还有一些关键的注意点：

首先，归并排序的拆分步骤是并行化的黄金切入点：当你把数组拆成左右两半后，这两个子数组的排序操作完全独立，不需要互相等待，所以可以同时交给不同的线程处理。等两边都排好序之后，再串行执行合并操作（合并阶段并行化的收益很低，还容易引入同步问题，所以没必要）。

如果你已经有了串行的归并排序代码，这种方式改动最小。我们用线程池来管理并发任务，避免频繁创建销毁线程的开销：

import java.util.Arrays;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class ConcurrentMergeSort {
    // 根据CPU核心数创建线程池，平衡并行度和开销
    private static final ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());

    public void mergeSort(int[] arr) {
        // 小数组用串行排序，避免线程开销（阈值可以自己调，比如1000）
        if (arr.length <= 1000) {
            Arrays.sort(arr);
            return;
        }
        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);

        // 提交左右排序任务到线程池
        Future<?> leftFuture = executor.submit(() -> mergeSort(leftSubArray));
        Future<?> rightFuture = executor.submit(() -> mergeSort(rightSubArray));

        // 等待两个任务都完成，再执行合并
        try {
            leftFuture.get();
            rightFuture.get();
        } catch (Exception e) {
            Thread.currentThread().interrupt();
            throw new RuntimeException("排序任务执行失败", e);
        }

        merge(arr, leftSubArray, rightSubArray);
    }

    // 你的合并逻辑参考（应该已经实现了）
    private void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        while (i < left.length) result[k++] = left[i++];
        while (j < right.length) result[k++] = right[j++];
    }

    // 程序结束前记得关闭线程池，否则JVM不会退出
    public static void shutdownExecutor() {
        executor.shutdown();
        try {
            if (!executor.awaitTermination(60, java.util.concurrent.TimeUnit.SECONDS)) {
                executor.shutdownNow();
            }
        } catch (InterruptedException e) {
            executor.shutdownNow();
            Thread.currentThread().interrupt();
        }
    }
}

Java的ForkJoinPool专门为递归拆分的并行任务设计，它会自动管理线程，避免过度创建线程，性能更优。这也是JDK自带的Arrays.parallelSort的底层实现思路：

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

public class ForkJoinMergeSort extends RecursiveAction {
    private final int[] arr;
    private final int start;
    private final int end;
    // 小数组阈值：当区间小于等于这个值时，用串行排序
    private static final int THRESHOLD = 1000;

    // 对外暴露的入口方法
    public static void sort(int[] arr) {
        ForkJoinPool pool = new ForkJoinPool();
        pool.invoke(new ForkJoinMergeSort(arr));
        pool.shutdown();
    }

    private ForkJoinMergeSort(int[] arr) {
        this(arr, 0, arr.length - 1);
    }

    private ForkJoinMergeSort(int[] arr, int start, int end) {
        this.arr = arr;
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute() {
        // 小区间用串行排序，避免线程开销
        if (end - start <= THRESHOLD) {
            Arrays.sort(arr, start, end + 1);
            return;
        }
        int mid = (start + end) / 2;
        // 拆分左右任务
        ForkJoinMergeSort leftTask = new ForkJoinMergeSort(arr, start, mid);
        ForkJoinMergeSort rightTask = new ForkJoinMergeSort(arr, mid + 1, end);
        // 并行执行左右任务，invokeAll会自动等待子任务完成
        invokeAll(leftTask, rightTask);
        // 合并结果
        merge(start, mid, end);
    }

    private void merge(int start, int mid, int end) {
        int[] temp = Arrays.copyOfRange(arr, start, end + 1);
        int i = start, j = mid + 1, k = 0;
        while (i <= mid && j <= end) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= end) temp[k++] = arr[j++];
        // 把临时数组复制回原数组
        System.arraycopy(temp, 0, arr, start, temp.length);
    }
}

• 小数组阈值：一定要设置一个阈值，当子数组/区间足够小时，改用串行排序。因为创建线程、调度线程的开销是固定的，对于很小的数组，串行排序的速度反而比并发快。这个阈值可以根据你的测试调整，一般在几百到几千之间。
• 线程安全：不用担心线程安全问题，因为每个线程处理的都是独立的子数组或者原数组的不同区间，没有共享的可变状态。
• 资源回收：线程池使用完毕后一定要关闭，否则JVM进程会一直挂着不退出。
• 异常处理：并发任务中要捕获并处理异常，避免某个线程的异常导致整个排序任务静默失败。

内容的提问来源于stack exchange，提问作者Arefe