ForkJoinPool ⭐

// 获取 common pool 实例
ForkJoinPool commonPool = ForkJoinPool.commonPool(); // 全局共享，所有并行流默认使用这个池
 
// 查看默认并行度
int parallelism = commonPool.getParallelism(); // 通常等于 CPU 核心数 - 1
System.out.println("Common pool parallelism: " + parallelism); // 例如 8 核机器输出 7
 
// 也可以通过 JVM 参数修改默认并行度
// -Djava.util.concurrent.ForkJoinPool.common.parallelism=16

// 为特定任务创建独立的 ForkJoinPool，避免污染 common pool
ForkJoinPool customPool = new ForkJoinPool(4); // 指定并行度为 4
customPool.submit(() -> {
    // 这里的并行流操作将使用 customPool 而非 commonPool
    myList.parallelStream()
          .map(item -> blockingApiCall(item)) // 阻塞操作不会影响全局 common pool
          .collect(Collectors.toList());
}).get(); // 等待完成
customPool.shutdown(); // 使用完毕后关闭自定义池

// === ForkJoinPool：线程池本身 ===
ForkJoinPool pool = new ForkJoinPool();          // 使用默认并行度(CPU核心数)
ForkJoinPool pool2 = new ForkJoinPool(8);        // 指定 8 个工作线程
ForkJoinPool common = ForkJoinPool.commonPool();  // 获取全局共享池
 
// === ForkJoinTask：所有 Fork/Join 任务的抽象基类 ===
// 通常不直接使用，而是使用下面两个子类
 
// === RecursiveTask<V>：有返回值的分治任务 ===
// 必须实现 compute() 方法，返回类型为 V
class SumTask extends RecursiveTask<Long> {
    @Override
    protected Long compute() {
        // 拆分逻辑 + 计算逻辑
        return result; // 返回计算结果
    }
}
 
// === RecursiveAction：无返回值的分治任务 ===
// 必须实现 compute() 方法，返回 void
class SortTask extends RecursiveAction {
    @Override
    protected void compute() {
        // 拆分逻辑 + 原地排序等操作，无需返回值
    }
}
 
// === 核心方法 ===
task.fork();           // 异步提交任务到当前线程的工作队列
Long result = task.join(); // 阻塞等待任务完成并获取结果
pool.invoke(task);     // 提交任务并等待结果（等于 fork + join）
pool.submit(task);     // 异步提交任务，返回 ForkJoinTask（Future）

public class MergeSort {
 
    // 入口方法：对 arr 的 [left, right] 区间进行归并排序
    public static void mergeSort(int[] arr, int left, int right) {
        // Base Case：当区间只剩一个元素（或无效区间），无需排序，直接返回
        if (left >= right) {
            return;
        }
 
        // ① Divide：计算中间位置，将数组一分为二
        int mid = left + (right - left) / 2;
 
        // ② Conquer：递归地对左半部分排序
        mergeSort(arr, left, mid);
 
        // ② Conquer：递归地对右半部分排序
        mergeSort(arr, mid + 1, right);
 
        // ③ Combine：将两个已排序的子数组合并为一个有序数组
        merge(arr, left, mid, right);
    }
 
    // 合并 [left, mid] 和 [mid+1, right] 两个有序子数组
    private static void merge(int[] arr, int left, int mid, int right) {
        // 创建临时数组，用于暂存合并结果
        int[] temp = new int[right - left + 1];
 
        // i 指向左半部分的起始位置
        int i = left;
        // j 指向右半部分的起始位置
        int j = mid + 1;
        // k 指向临时数组的当前写入位置
        int k = 0;
 
        // 依次比较两个子数组的元素，将较小的放入 temp
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                // 左侧元素更小（或相等），写入 temp 并移动左指针
                temp[k++] = arr[i++];
            } else {
                // 右侧元素更小，写入 temp 并移动右指针
                temp[k++] = arr[j++];
            }
        }
 
        // 左半部分可能还有剩余元素，全部追加到 temp
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
 
        // 右半部分可能还有剩余元素，全部追加到 temp
        while (j <= right) {
            temp[k++] = arr[j++];
        }
 
        // 将合并结果从 temp 复制回原数组的对应位置
        System.arraycopy(temp, 0, arr, left, temp.length);
    }
}

// 串行版本：顺序执行
mergeSort(arr, left, mid);      // 先执行这个
mergeSort(arr, mid + 1, right); // 等上面完成后才执行这个
 
// 并行版本（伪代码）：同时执行
fork(() -> mergeSort(arr, left, mid));      // 异步提交给其他线程
fork(() -> mergeSort(arr, mid + 1, right)); // 异步提交给其他线程
joinAll();  // 等待两个子任务都完成
merge(arr, left, mid, right);  // 合并结果

// 继承 RecursiveTask<Long>，表示有返回值的分治任务
public class SumTask extends RecursiveTask<Long> {
 
    // 阈值：当数组片段小于此值时，不再拆分，直接串行计算
    private static final int THRESHOLD = 10_000;
 
    // 待处理的数组
    private final long[] array;
    // 当前任务负责的区间 [start, end)
    private final int start;
    private final int end;
 
    // 构造方法：指定数组和处理范围
    public SumTask(long[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }
 
    @Override
    protected Long compute() {
        int length = end - start;
 
        // ===== Base Case：规模足够小，直接串行求和 =====
        if (length <= THRESHOLD) {
            long sum = 0;
            // 简单循环累加，不再递归拆分
            for (int i = start; i < end; i++) {
                sum += array[i];
            }
            return sum;
        }
 
        // ===== Divide：将任务一分为二 =====
        int mid = start + length / 2;
        // 创建左半部分子任务
        SumTask leftTask = new SumTask(array, start, mid);
        // 创建右半部分子任务
        SumTask rightTask = new SumTask(array, mid, end);
 
        // ===== Fork：异步提交左子任务到线程池 =====
        leftTask.fork();
 
        // ===== Conquer：当前线程直接计算右子任务（避免浪费当前线程） =====
        long rightResult = rightTask.compute();
 
        // ===== Join：等待左子任务完成并获取结果 =====
        long leftResult = leftTask.join();
 
        // ===== Combine：合并两个子结果 =====
        return leftResult + rightResult;
    }
}

/*
 *  WorkQueue (基于数组的双端队列)
 *
 *  ┌───────────────────────────────────────────────────┐
 *  │  array[]  (环形数组，容量为 2 的幂)                  │
 *  │                                                     │
 *  │  Index:   0     1     2     3     4     5     6     │
 *  │         ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐│
 *  │         │     │ T-A │ T-B │ T-C │ T-D │ T-E │     ││
 *  │         └─────┴─────┴─────┴─────┴─────┴─────┴─────┘│
 *  │           ▲                               ▲         │
 *  │           │                               │         │
 *  │         base                             top        │
 *  │      (Stealer 端)                    (Owner 端)     │
 *  │                                                     │
 *  │   ◀── steal() 从 base 端取      push()/pop() ──▶   │
 *  │       (其他空闲线程)              (拥有者线程自己)     │
 *  └───────────────────────────────────────────────────┘
 *
 *  - Owner 线程调用 fork() 时 → push 到 top 端 (top++)
 *  - Owner 线程需要子结果时 → pop 从 top 端取 (top--)
 *  - Stealer 窃取时 → 从 base 端取走最老的任务 (base++)
 *  - 仅当 top == base + 1（剩最后一个元素）时才需要 CAS 竞争
 */

// === ForkJoinPool 工作窃取核心伪代码 ===
 
// 每个 Worker Thread 的主循环
void runWorker(ForkJoinWorkerThread wt) {
    WorkQueue myQueue = wt.workQueue;   // 获取当前线程的私有双端队列
 
    while (!isTerminated()) {           // 线程池未关闭就一直循环
        ForkJoinTask<?> task;
 
        // 第一步：尝试从自己的 Deque Top 端 pop 任务（LIFO）
        task = myQueue.pop();           // 无锁操作，最快路径
 
        if (task != null) {
            task.doExec();              // 直接执行任务
            continue;                   // 继续下一轮循环
        }
 
        // 第二步：自己队列为空，进入窃取模式
        task = scan(wt, myQueue);       // 随机扫描其他 Worker 的队列
 
        if (task != null) {
            task.doExec();              // 执行偷来的任务
            continue;                   // 偷到了就继续干活
        }
 
        // 第三步：所有队列都空了，尝试休眠等待
        awaitWork(wt);                  // 挂起线程，等待新任务到来
    }
}
 
// scan 方法：随机选择一个 victim 队列，从 Base 端窃取
ForkJoinTask<?> scan(ForkJoinWorkerThread wt, WorkQueue myQueue) {
    WorkQueue[] ws = workQueues;        // 获取所有 Worker 的队列数组
    int n = ws.length;                  // 队列总数
    int r = ThreadLocalRandom.current().nextInt(n); // 随机起始位置
 
    for (int i = 0; i < n; i++) {       // 遍历所有队列
        WorkQueue victim = ws[(r + i) & (n - 1)]; // 从随机位置开始轮询
 
        if (victim != null && victim.base < victim.top) { // 该队列有任务
            ForkJoinTask<?> t = victim.poll();  // 从 Base 端取（FIFO, CAS）
            if (t != null) {
                return t;               // 窃取成功，返回任务
            }
        }
    }
    return null;                        // 全部扫描完都没有，返回 null
}

import java.util.concurrent.RecursiveTask;
 
/**
 * 使用 RecursiveTask 实现并行数组求和
 * 泛型参数 Long 表示 compute() 的返回值类型
 */
public class SumTask extends RecursiveTask<Long> {
 
    // 阈值：当子数组长度 <= THRESHOLD 时，直接线性求和，不再拆分
    private static final int THRESHOLD = 1000;
 
    // 待求和数组的引用
    private final long[] array;
 
    // 当前任务负责的起始索引（包含）
    private final int start;
 
    // 当前任务负责的结束索引（不包含）
    private final int end;
 
    // 构造器：接收数组引用和当前任务负责的区间 [start, end)
    public SumTask(long[] array, int start, int end) {
        this.array = array;   // 所有子任务共享同一个数组引用，不会拷贝
        this.start = start;
        this.end = end;
    }
 
    /**
     * 核心计算方法 - 由 ForkJoinPool 中的工作线程调用
     * @return 区间 [start, end) 内所有元素的和
     */
    @Override
    protected Long compute() {
        // 计算当前任务负责的元素数量
        int length = end - start;
 
        // ★ Base case: 任务粒度足够小，直接计算
        if (length <= THRESHOLD) {
            long sum = 0;                     // 累加器
            for (int i = start; i < end; i++) {
                sum += array[i];              // 逐个累加
            }
            return sum;                       // 直接返回结果，不再拆分
        }
 
        // ★ Recursive case: 任务太大，一分为二
        int mid = start + (length >> 1);      // 取中点，等价于 start + length/2
 
        // 创建左半部分子任务 [start, mid)
        SumTask leftTask = new SumTask(array, start, mid);
 
        // 创建右半部分子任务 [mid, end)
        SumTask rightTask = new SumTask(array, mid, end);
 
        // 将左子任务异步提交到 ForkJoinPool（由其他工作线程执行）
        leftTask.fork();
 
        // ★ 关键优化：右子任务在【当前线程】直接执行，避免不必要的线程切换
        Long rightResult = rightTask.compute();
 
        // 等待左子任务完成并获取其结果
        Long leftResult = leftTask.join();
 
        // 合并两个子任务的结果
        return leftResult + rightResult;
    }
}

import java.util.concurrent.RecursiveAction;
 
/**
 * 使用 RecursiveAction 将数组中每个元素翻倍（原地修改，无返回值）
 */
public class DoubleTask extends RecursiveAction {
 
    // 阈值：当子数组长度 <= THRESHOLD 时，直接处理
    private static final int THRESHOLD = 1000;
 
    // 待处理的数组引用（所有子任务共享同一数组）
    private final long[] array;
 
    // 当前任务负责的起始索引（包含）
    private final int start;
 
    // 当前任务负责的结束索引（不包含）
    private final int end;
 
    // 构造器
    public DoubleTask(long[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }
 
    /**
     * 核心计算方法 —— 注意返回值为 void
     */
    @Override
    protected void compute() {
        // 计算当前任务负责的元素数量
        int length = end - start;
 
        // ★ Base case: 直接处理
        if (length <= THRESHOLD) {
            for (int i = start; i < end; i++) {
                array[i] *= 2;               // 每个元素翻倍（原地修改）
            }
            return;                           // 无返回值，直接 return
        }
 
        // ★ Recursive case: 拆分为两个子任务
        int mid = start + (length >> 1);
 
        // 创建左、右子任务
        DoubleTask left = new DoubleTask(array, start, mid);
        DoubleTask right = new DoubleTask(array, mid, end);
 
        // invokeAll: 同时提交两个子任务并等待它们全部完成
        // 因为没有返回值需要合并，所以用 invokeAll 比 fork+compute 更简洁
        invokeAll(left, right);
    }
}

@Override
protected Long compute() {
    if (任务足够小) {
        return 直接计算();                     // Base case
    }
 
    // 拆分
    SubTask left = new SubTask(左半部分);      // 创建左子任务
    SubTask right = new SubTask(右半部分);      // 创建右子任务
 
    left.fork();                               // 左子任务异步推入队列
    Long rightResult = right.compute();        // 右子任务当前线程直接执行（关键优化！）
    Long leftResult = left.join();             // 等待左子任务完成
 
    return leftResult + rightResult;           // 合并结果
}

// 写法 A
leftTask.fork();
rightTask.fork();
return leftTask.join() + rightTask.join();
 
// 写法 B
leftTask.fork();
Long rightResult = rightTask.compute();
Long leftResult = leftTask.join();
return leftResult + rightResult;
 
// 写法 C
Long leftResult = leftTask.compute();
rightTask.fork();
Long rightResult = rightTask.join();
return leftResult + rightResult;
 
// 写法 D
invokeAll(leftTask, rightTask);
return leftTask.join() + rightTask.join();

import java.util.concurrent.ForkJoinPool;   // Fork/Join 线程池
import java.util.concurrent.RecursiveTask;  // 有返回值的递归任务
 
/**
 * 大数组并行求和任务
 * 继承 RecursiveTask<Long> 表示该任务会返回一个 Long 类型的计算结果
 */
public class ArraySumTask extends RecursiveTask<Long> {
 
    // 阈值：当子数组长度 <= THRESHOLD 时，直接顺序计算，不再继续拆分
    // 这个值的选取至关重要——太小会导致任务过多、调度开销大；太大则并行度不足
    private static final int THRESHOLD = 10_000;
 
    // 待求和的原始数组（所有子任务共享同一个数组引用，不复制数据）
    private final long[] array;
 
    // 当前子任务负责计算的区间：[start, end)（左闭右开）
    private final int start;
    private final int end;
 
    /**
     * 构造方法：指定数组及当前任务负责的区间
     * @param array 原始数组
     * @param start 起始索引（包含）
     * @param end   结束索引（不包含）
     */
    public ArraySumTask(long[] array, int start, int end) {
        this.array = array;  // 保存数组引用
        this.start = start;  // 保存起始位置
        this.end = end;      // 保存结束位置
    }
 
    /**
     * 核心计算逻辑——Fork/Join 框架会自动调用此方法
     * 这里体现了分治算法的精髓：要么直接算，要么拆分后递归
     */
    @Override
    protected Long compute() {
        // 计算当前区间的长度
        int length = end - start;
 
        // ====== 基线条件 (Base Case) ======
        // 如果区间足够小，直接用简单循环求和，避免继续拆分的开销
        if (length <= THRESHOLD) {
            long sum = 0L;                    // 初始化局部求和变量
            for (int i = start; i < end; i++) { // 遍历当前负责的区间
                sum += array[i];              // 逐个累加元素
            }
            return sum;                       // 返回这个小区间的和
        }
 
        // ====== 递归拆分 (Recursive Split) ======
        // 计算区间中点，将任务一分为二
        int mid = start + (length / 2);  // 避免 (start+end)/2 可能的溢出
 
        // 创建左半部分子任务：负责 [start, mid)
        ArraySumTask leftTask = new ArraySumTask(array, start, mid);
 
        // 创建右半部分子任务：负责 [mid, end)
        ArraySumTask rightTask = new ArraySumTask(array, mid, end);
 
        // ====== Fork 阶段 ======
        // 将左子任务异步提交到 ForkJoinPool 的工作队列
        // fork() 不会阻塞当前线程——它只是把任务推入双端队列的头部
        leftTask.fork();
 
        // ====== 关键优化：当前线程直接计算右子任务 ======
        // 不要对两个子任务都 fork()！那样当前线程就空闲了，浪费一个线程
        // 正确做法：fork 一个，当前线程直接 compute 另一个
        long rightResult = rightTask.compute();
 
        // ====== Join 阶段 ======
        // 等待左子任务完成并获取其结果
        // 如果左子任务已经完成，join() 会立即返回
        // 如果尚未完成，当前线程会尝试"窃取"其他任务来执行（而非空等）
        long leftResult = leftTask.join();
 
        // ====== 合并结果 ======
        // 将左右两半的和相加，得到当前区间的总和
        return leftResult + rightResult;
    }
 
    /**
     * 主方法：演示如何创建 ForkJoinPool 并提交任务
     */
    public static void main(String[] args) {
        // 准备测试数据：创建一个包含 1000 万个元素的数组
        int size = 10_000_000;
        long[] numbers = new long[size];
 
        // 用简单规则填充数组：array[i] = i + 1，即 1, 2, 3, ..., 10000000
        for (int i = 0; i < size; i++) {
            numbers[i] = i + 1L;  // +1L 确保使用 long 运算
        }
 
        // 创建 ForkJoinPool 实例
        // 无参构造器默认使用 Runtime.availableProcessors() 个工作线程
        // 例如 8 核 CPU 就创建 8 个工作线程
        ForkJoinPool pool = new ForkJoinPool();
 
        // 创建根任务：覆盖整个数组区间 [0, size)
        ArraySumTask rootTask = new ArraySumTask(numbers, 0, size);
 
        // invoke() = 同步提交 + 等待结果，等价于 submit(task).join()
        // 它会阻塞当前主线程，直到整个分治计算完成
        long result = pool.invoke(rootTask);
 
        // 输出结果
        System.out.println("Fork/Join 求和结果: " + result);
 
        // 验证正确性：等差数列求和公式 n*(n+1)/2
        long expected = (long) size * (size + 1) / 2;
        System.out.println("数学公式验证结果: " + expected);
        System.out.println("结果是否一致: " + (result == expected));
 
        // 输出线程池状态信息（调试用）
        System.out.println("并行度 (Parallelism): " + pool.getParallelism());
        System.out.println("线程池大小 (Pool Size): " + pool.getPoolSize());
        System.out.println("窃取次数 (Steal Count): " + pool.getStealCount());
 
        // 关闭线程池，释放资源
        pool.shutdown();
    }
}

Fork/Join 求和结果: 50000005000000
数学公式验证结果: 50000005000000
结果是否一致: true
并行度 (Parallelism): 8
线程池大小 (Pool Size): 8
窃取次数 (Steal Count): 12

import java.io.File;                        // 文件/目录操作
import java.util.ArrayList;                  // 存储子任务列表
import java.util.List;                       // List 接口
import java.util.concurrent.ForkJoinPool;    // Fork/Join 线程池
import java.util.concurrent.RecursiveTask;   // 有返回值的递归任务
 
/**
 * 递归统计目录总大小（字节数）
 * 每个目录拆分为"子目录任务" + "当前目录下文件大小直接累加"
 */
public class DirectorySizeTask extends RecursiveTask<Long> {
 
    // 当前任务需要统计的目录
    private final File directory;
 
    /**
     * 构造方法
     * @param directory 要统计大小的目录
     */
    public DirectorySizeTask(File directory) {
        this.directory = directory;  // 保存目录引用
    }
 
    @Override
    protected Long compute() {
        long totalSize = 0L;  // 当前目录的累计大小
 
        // 获取目录下的所有文件和子目录
        // listFiles() 可能返回 null（如果路径不存在或没有权限）
        File[] files = directory.listFiles();
 
        // 防御性检查：目录为空或无法访问时直接返回 0
        if (files == null || files.length == 0) {
            return 0L;
        }
 
        // 用于收集所有子目录对应的异步任务
        List<DirectorySizeTask> subTasks = new ArrayList<>();
 
        // 遍历目录下的每个条目
        for (File file : files) {
            if (file.isFile()) {
                // 如果是普通文件 → 直接累加其大小（基线条件）
                totalSize += file.length();
            } else if (file.isDirectory()) {
                // 如果是子目录 → 创建新的子任务
                DirectorySizeTask subTask = new DirectorySizeTask(file);
                subTask.fork();          // 异步提交到工作队列
                subTasks.add(subTask);   // 记录下来，稍后 join
            }
        }
 
        // 等待所有子目录任务完成，并累加它们的结果
        for (DirectorySizeTask subTask : subTasks) {
            totalSize += subTask.join();  // join() 阻塞直到该子任务完成
        }
 
        // 返回当前目录（含所有子目录）的总大小
        return totalSize;
    }
 
    public static void main(String[] args) {
        // 指定要统计的根目录（请替换为你系统上的实际路径）
        File rootDir = new File("/Users/developer/projects");
 
        // 使用公共 ForkJoinPool（也可以 new ForkJoinPool()）
        ForkJoinPool pool = ForkJoinPool.commonPool();
 
        // 创建根任务
        DirectorySizeTask rootTask = new DirectorySizeTask(rootDir);
 
        // 同步执行并获取结果
        long totalBytes = pool.invoke(rootTask);
 
        // 格式化输出
        System.out.printf("目录: %s%n", rootDir.getAbsolutePath());
        System.out.printf("总大小: %,d bytes (%.2f MB)%n",
                totalBytes,                           // 原始字节数
                totalBytes / (1024.0 * 1024.0));      // 转换为 MB
    }
}

import java.util.Arrays;                      // Arrays.copyOfRange, Arrays.toString
import java.util.concurrent.ForkJoinPool;      // Fork/Join 线程池
import java.util.concurrent.RecursiveAction;   // 无返回值的递归任务
 
/**
 * 并行归并排序
 * 继承 RecursiveAction —— 原地修改数组，不返回结果
 */
public class ParallelMergeSort extends RecursiveAction {
 
    // 阈值：小于此长度时退化为插入排序（小数组插入排序更快）
    private static final int THRESHOLD = 4096;
 
    // 待排序数组
    private final int[] array;
 
    // 当前任务负责的区间 [start, end)
    private final int start;
    private final int end;
 
    /**
     * 构造方法
     * @param array 待排序数组（原地修改）
     * @param start 起始索引（包含）
     * @param end   结束索引（不包含）
     */
    public ParallelMergeSort(int[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }
 
    @Override
    protected void compute() {  // 注意：返回类型是 void（RecursiveAction 的特征）
        int length = end - start;
 
        // ====== 基线条件：小数组使用插入排序 ======
        if (length <= THRESHOLD) {
            insertionSort(array, start, end);  // 插入排序对小数组极其高效
            return;                             // 直接返回，不再拆分
        }
 
        // ====== 递归拆分 ======
        int mid = start + (length / 2);  // 计算中点
 
        // 创建左半部分排序子任务
        ParallelMergeSort leftSort = new ParallelMergeSort(array, start, mid);
 
        // 创建右半部分排序子任务
        ParallelMergeSort rightSort = new ParallelMergeSort(array, mid, end);
 
        // ====== 并行执行两个子任务 ======
        // invokeAll() 是一个便捷方法，等价于：
        //   leftSort.fork();
        //   rightSort.compute();
        //   leftSort.join();
        // 但 invokeAll 内部做了更好的优化——它会自动决定哪个任务 fork、哪个 compute
        invokeAll(leftSort, rightSort);
 
        // ====== 合并两个已排序的子数组 ======
        // 此时 array[start..mid) 和 array[mid..end) 各自已有序
        // 需要将它们合并成一个有序序列
        merge(array, start, mid, end);
    }
 
    /**
     * 经典的双指针归并操作
     * 将 array[start..mid) 和 array[mid..end) 合并为有序序列
     */
    private void merge(int[] arr, int start, int mid, int end) {
        // 创建左半部分的临时拷贝
        int[] left = Arrays.copyOfRange(arr, start, mid);
        // 创建右半部分的临时拷贝
        int[] right = Arrays.copyOfRange(arr, mid, end);
 
        int i = 0;      // 左数组的游标
        int j = 0;      // 右数组的游标
        int k = start;   // 原数组的写入位置
 
        // 双指针逐一比较，较小的先放入原数组
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {       // <= 保证稳定性（stable sort）
                arr[k++] = left[i++];        // 取左边元素
            } else {
                arr[k++] = right[j++];       // 取右边元素
            }
        }
 
        // 左数组可能还有剩余元素
        while (i < left.length) {
            arr[k++] = left[i++];
        }
 
        // 右数组可能还有剩余元素
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }
 
    /**
     * 插入排序：对小规模数组非常高效
     * 时间复杂度 O(n^2)，但常数因子小，且对近乎有序的数组接近 O(n)
     */
    private void insertionSort(int[] arr, int start, int end) {
        for (int i = start + 1; i < end; i++) {  // 从第二个元素开始
            int key = arr[i];                     // 当前要插入的元素
            int j = i - 1;                        // 从 key 左边开始向前扫描
            while (j >= start && arr[j] > key) {  // 找到 key 应该插入的位置
                arr[j + 1] = arr[j];              // 元素右移，腾出空位
                j--;                               // 继续向前
            }
            arr[j + 1] = key;                     // 将 key 插入正确位置
        }
    }
 
    public static void main(String[] args) {
        // 构造测试数据：100 万个随机整数
        int size = 1_000_000;
        int[] data = new int[size];
        java.util.Random random = new java.util.Random(42);  // 固定种子保证可复现
        for (int i = 0; i < size; i++) {
            data[i] = random.nextInt(size);  // [0, size) 范围内的随机整数
        }
 
        // 复制一份用于验证（Arrays.sort 作为参照基准）
        int[] expected = data.clone();  // 深拷贝
 
        // ====== Fork/Join 并行排序 ======
        ForkJoinPool pool = new ForkJoinPool();
        long startTime = System.nanoTime();                         // 开始计时
 
        // 创建根任务并执行
        pool.invoke(new ParallelMergeSort(data, 0, data.length));
 
        long elapsed = System.nanoTime() - startTime;               // 计算耗时
        System.out.printf("Fork/Join 并行归并排序: %.3f ms%n",
                elapsed / 1_000_000.0);
 
        // ====== 对照组：JDK 内置排序 ======
        startTime = System.nanoTime();
        Arrays.sort(expected);                                       // 双轴快排
        elapsed = System.nanoTime() - startTime;
        System.out.printf("Arrays.sort 排序:      %.3f ms%n",
                elapsed / 1_000_000.0);
 
        // 验证排序结果是否一致
        System.out.println("排序结果一致: " + Arrays.equals(data, expected));
 
        pool.shutdown();  // 释放资源
    }
}

// invokeAll(task1, task2) 的等价伪代码
public static void invokeAll(ForkJoinTask<?> t1, ForkJoinTask<?> t2) {
    t2.fork();       // 把第二个任务异步提交
    t1.compute();    // 当前线程直接执行第一个任务（不浪费线程！）
    t2.join();       // 等待第二个任务完成
}

import java.util.List;                        // 任务列表
import java.util.concurrent.ForkJoinPool;      // Fork/Join 线程池
import java.util.concurrent.RecursiveAction;   // 无返回值任务
 
/**
 * 批量图片处理任务
 * 将大批量图片列表拆分成小批次并行处理
 */
public class ImageProcessTask extends RecursiveAction {
 
    // 阈值：每批最多处理 5 张图片
    private static final int THRESHOLD = 5;
 
    // 待处理的图片路径列表
    private final List<String> imagePaths;
 
    // 当前任务负责的区间 [start, end)
    private final int start;
    private final int end;
 
    public ImageProcessTask(List<String> imagePaths, int start, int end) {
        this.imagePaths = imagePaths;  // 共享同一个列表引用
        this.start = start;
        this.end = end;
    }
 
    @Override
    protected void compute() {
        int length = end - start;
 
        // ====== 基线条件：直接处理这批图片 ======
        if (length <= THRESHOLD) {
            for (int i = start; i < end; i++) {
                processImage(imagePaths.get(i));  // 逐张处理
            }
            return;
        }
 
        // ====== 拆分成两个子批次 ======
        int mid = start + (length / 2);
 
        ImageProcessTask leftBatch = new ImageProcessTask(imagePaths, start, mid);
        ImageProcessTask rightBatch = new ImageProcessTask(imagePaths, mid, end);
 
        // invokeAll 自动处理 fork/compute/join 的最优顺序
        invokeAll(leftBatch, rightBatch);
    }
 
    /**
     * 模拟单张图片的处理逻辑（实际项目中这里是 BufferedImage 缩放操作）
     */
    private void processImage(String path) {
        // 获取当前执行线程的名称（便于观察并行效果）
        String threadName = Thread.currentThread().getName();
        System.out.printf("[%s] 正在处理: %s%n", threadName, path);
 
        try {
            Thread.sleep(50);  // 模拟图片处理耗时 50ms
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();  // 恢复中断标志
        }
    }
 
    public static void main(String[] args) {
        // 构造 20 张模拟图片路径
        List<String> images = new java.util.ArrayList<>();
        for (int i = 1; i <= 20; i++) {
            images.add("/photos/image_" + String.format("%03d", i) + ".jpg");
        }
 
        ForkJoinPool pool = new ForkJoinPool(4);  // 指定 4 个工作线程
 
        long startTime = System.currentTimeMillis();
 
        // 提交根任务：处理全部 20 张图片
        pool.invoke(new ImageProcessTask(images, 0, images.size()));
 
        long elapsed = System.currentTimeMillis() - startTime;
 
        System.out.println("============================");
        System.out.printf("全部处理完成! 总耗时: %d ms%n", elapsed);
        System.out.printf("理论串行耗时: %d ms%n", 20 * 50);  // 20 * 50 = 1000ms
        System.out.printf("并行加速比: %.2fx%n", (20.0 * 50) / elapsed);
 
        pool.shutdown();
    }
}

[ForkJoinPool-1-worker-1] 正在处理: /photos/image_001.jpg
[ForkJoinPool-1-worker-3] 正在处理: /photos/image_011.jpg
[ForkJoinPool-1-worker-2] 正在处理: /photos/image_006.jpg
[ForkJoinPool-1-worker-4] 正在处理: /photos/image_016.jpg
... (四个线程交错并行)
============================
全部处理完成! 总耗时: 263 ms
理论串行耗时: 1000 ms
并行加速比: 3.80x

// ① invoke: 同步提交并阻塞，直到拿到结果（最常用）
Long result = pool.invoke(task);
 
// ② submit: 异步提交，立即返回 ForkJoinTask（即 Future）
ForkJoinTask<Long> future = pool.submit(task);
Long result = future.get();  // 可在稍后某个时刻获取结果
 
// ③ execute: 异步提交，无返回值（配合 RecursiveAction）
pool.execute(task);
// ... 做其他事 ...
task.join();  // 需要时手动等待
 
// ④ fork: 只在 compute() 方法内部使用，将子任务推入队列
leftTask.fork();            // 提交到当前工作线程的双端队列
Long right = rightTask.compute();  // 当前线程直接计算
Long left = leftTask.join();       // 等待 fork 出去的任务

// 方式一：使用 JVM 全局共享的公共池（Java 8+ 的并行流也用这个池）
ForkJoinPool common = ForkJoinPool.commonPool();
 
// 方式二：创建独立的池（推荐用于生产环境的关键路径）
ForkJoinPool dedicated = new ForkJoinPool(
    Runtime.getRuntime().availableProcessors()  // 并行度
);