基于ConcurrentLinkedQueue的并发归并排序实现问题求助

你的代码出现无序输出的核心原因是任务执行顺序没有保障，合并操作在左右子数组排序完成前就开始执行，加上线程管理混乱导致的执行时序问题，具体问题和修复方案如下：

原代码的核心问题 #

• 重复创建线程：每次调用startWorkerThreads()都会生成M个新线程，线程数量爆炸且没有等待任务完成，导致合并逻辑提前执行。
• 无任务依赖控制：合并任务直接入队，没有机制确保左右子数组的排序任务全部完成后才执行合并。
• 主线程未等待排序结束：main函数调用mergeSort后立即打印结果，此时排序可能还在后台运行。

修复后的代码 #

import java.util.Arrays;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.CountDownLatch;

public class Main {
    private static final int M = 4; // 工作线程数量
    private static final ConcurrentLinkedQueue<Runnable> taskQueue = new ConcurrentLinkedQueue<>();

    // 初始化固定数量的工作线程，仅创建一次
    static {
        for (int i = 0; i < M; i++) {
            new Thread(() -> {
                Runnable task;
                while ((task = taskQueue.poll()) != null) {
                    task.run();
                }
            }).start();
        }
    }

    public static void main(String[] args) throws InterruptedException {
        int[] input = new int[100];
        for (int i = 0; i < input.length; i++) {
            input[i] = (int) (Math.random() * 100);
        }

        // 全局计数器，等待整个排序任务完成
        CountDownLatch globalFinishLatch = new CountDownLatch(1);
        taskQueue.offer(() -> {
            mergeSort(input, 0, input.length - 1);
            globalFinishLatch.countDown();
        });

        globalFinishLatch.await(); // 阻塞主线程，直到排序完成
        System.out.println(Arrays.toString(input));
    }

    private static void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            // 计数器，等待左右两个子排序任务完成
            CountDownLatch subTaskLatch = new CountDownLatch(2);

            // 提交左子数组排序任务
            taskQueue.offer(() -> {
                mergeSort(arr, l, m);
                subTaskLatch.countDown();
            });
            // 提交右子数组排序任务
            taskQueue.offer(() -> {
                mergeSort(arr, m + 1, r);
                subTaskLatch.countDown();
            });

            try {
                subTaskLatch.await(); // 等待左右子数组排序完成，再执行合并
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                return;
            }

            // 左右子数组排序完成后执行合并
            merge(arr, l, m, r);
        }
    }

    private static void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int[] left = new int[n1];
        int[] right = new int[n2];

        // 替换手动拷贝为System.arraycopy，更高效简洁
        System.arraycopy(arr, l, left, 0, n1);
        System.arraycopy(arr, m + 1, right, 0, n2);

        int i = 0, j = 0, k = l;
        while (i < n1 && j < n2) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = right[j];
            j++;
            k++;
        }
    }
}

关键修改说明 #

1. 固定工作线程：通过静态代码块初始化M个工作线程，持续从任务队列中取任务执行，避免重复创建线程的资源浪费和时序混乱。
2. CountDownLatch控制依赖：
   • subTaskLatch用于等待左右两个子排序任务完成，确保合并操作只有在前置条件满足时才执行。
   • globalFinishLatch让主线程等待整个排序流程结束，避免提前打印未完成排序的数组。
3. 优化数组拷贝：用System.arraycopy替代手动循环拷贝，提升代码效率和可读性。

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