多线程归并排序性能不及单线程？求代码问题排查

嘿，我完全理解你的困惑——本来预期多线程归并排序能更早展现速度优势，结果只有数组规模破百万时才略快，提升还不明显。咱们来拆解下你的代码里的几个核心问题，以及对应的优化方向：

1. 线程创建的开销被忽略了 #

你现在的实现里，每次递归拆分都新建一个Thread对象，但线程的创建、调度和上下文切换是有不小开销的。当数组规模较小时，排序本身的耗时可能还比不上线程操作的开销，反而拖慢了整体速度。这就是为什么小数据量下多线程版本反而更慢的核心原因。

优化建议： #

设置一个阈值（比如5000或10000，可根据你的环境调整），当子数组的大小小于这个阈值时，直接用单线程排序，避免不必要的线程开销。

2. 线程利用率极低 #

你的代码每次只给左半部分分配一个新线程，右半部分还是由主线程处理——这意味着最多只能同时运行2个线程。如果你的CPU是多核的（现在基本都是），剩下的核心完全没被利用起来，自然性能提升不明显。

优化建议： #

• 用线程池来管理线程，避免频繁创建销毁线程；
• 更推荐用Java专门为分治任务设计的ForkJoinPool，它会自动根据CPU核心数调整线程数量，高效分配任务，避免过度调度。

3. 额外的内存开销（次要，但可优化） #

你的merge方法每次都新建临时数组，虽然对多线程和单线程的影响一致，但频繁的数组创建销毁也会带来额外开销。如果要进一步优化，可以考虑复用临时数组，但这个对性能的影响远不如前两点。

改进后的带阈值多线程版本示例 #

public class Sorter {
    // 自定义阈值：子数组小于该值时用单线程
    private static final int SORT_THRESHOLD = 5000;

    public void mergeSortMultiThread(int[] array, int start, int end) {
        // 小数据量直接用单线程，避免线程开销
        if (end - start + 1 <= SORT_THRESHOLD) {
            mergeSortSequence(array, start, end);
            return;
        }

        if (start < end) {
            int mid = (start + end) / 2;
            Thread leftThread = new Thread(() -> mergeSortMultiThread(array, start, mid));
            leftThread.start();
            // 右半部分也递归用多线程（如果超过阈值）
            mergeSortMultiThread(array, mid + 1, end);
            
            try {
                leftThread.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            merge(array, start, mid, end);
        }
    }

    // 你的单线程排序方法保持不变
    public void mergeSortSequence(int[] array, int start, int end) {
        if (start < end) {
            int m = (start + end) / 2;
            mergeSortSequence(array, start, m);
            mergeSortSequence(array, m + 1, end);
            merge(array, start, m, end);
        }
    }

    // 你的merge方法保持不变
    private void merge(int arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int[n1];
        int R[] = new int[n2];
        
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
            
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}

更高效的ForkJoin版本示例 #

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

public class MergeSortForkJoin extends RecursiveAction {
    private int[] array;
    private int start;
    private int end;
    private static final int SORT_THRESHOLD = 5000;

    public MergeSortForkJoin(int[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute() {
        // 小数据量用单线程
        if (end - start + 1 <= SORT_THRESHOLD) {
            mergeSortSequence(array, start, end);
            return;
        }

        int mid = (start + end) / 2;
        // 创建左右子任务
        MergeSortForkJoin leftTask = new MergeSortForkJoin(array, start, mid);
        MergeSortForkJoin rightTask = new MergeSortForkJoin(array, mid + 1, end);
        
        // 并行执行两个子任务
        invokeAll(leftTask, rightTask);
        // 合并结果
        merge(array, start, mid, end);
    }

    private void mergeSortSequence(int[] array, int start, int end) {
        if (start < end) {
            int m = (start + end) / 2;
            mergeSortSequence(array, start, m);
            mergeSortSequence(array, m + 1, end);
            merge(array, start, m, end);
        }
    }

    private void merge(int arr[], int l, int m, int r) {
        // 原merge代码不变
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int[n1];
        int R[] = new int[n2];
        
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
            
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // 使用方式示例：
    // public static void main(String[] args) {
    //     int[] array = new int[1000000];
    //     // 初始化数组...
    //     ForkJoinPool pool = new ForkJoinPool();
    //     pool.invoke(new MergeSortForkJoin(array, 0, array.length - 1));
    // }
}

最后补充两个测试小技巧：

1. 预热JVM：第一次运行代码时，JVM会进行JIT编译，耗时会偏高。建议先跑几次空测试，再正式统计耗时；
2. 取平均值：多次测试取平均耗时，避免单次测试的偶然因素影响结果。

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