Java并行归并排序结果不稳定问题排查求助

核心原因：合并阶段的线程安全与竞态条件 #

你的问题大概率出在MergeTask的多线程合并逻辑中，由于并发操作共享数组时的竞态条件，导致数组元素被覆盖、写入错误值（比如Long.MIN_VALUE），最终出现时对时错的结果。

常见问题点及排查方向 #

• 共享数组的并发读写冲突
  如果MergeTask直接在原始数组上执行合并操作（边读原数组元素边写入合并结果），多个线程同时操作数组的相邻或重叠区间时，会出现读写冲突：线程A读取某索引元素的同时，线程B可能正在修改该位置，导致A读取到错误值并写入最终结果，或者B的写入覆盖了A的结果。

• 合并区间划分错误
  若拆分任务时左右区间的边界计算有误，会导致多个MergeTask同时操作同一个数组索引范围。比如某索引被两个线程同时写入，最终值取决于最后执行的线程，结果就会随机出错。

• 临时数组未独立分配
  如果多个MergeTask共享同一个临时数组，不同任务的合并数据会互相干扰：任务A的临时合并结果被任务B覆盖，写入原数组时就会出现错误值。

• 子任务未完全完成就执行合并
  如果MergeSortTask在发起子排序任务后，未等待所有子任务完成就启动MergeTask，会读取到未排序的数组元素，导致合并结果彻底错误。

修复建议 #

1. 隔离合并操作的临时空间
   每个MergeTask单独创建临时数组，先将需要合并的左右区间元素复制到临时数组中完成合并，再一次性将合并结果复制回原数组的对应区间。避免在原数组上直接进行合并的读写交叉操作。

2. 严格保证合并区间的独立性
   确认每个MergeTask负责的原数组区间[left, right]完全独立，与其他MergeTask的区间无重叠。比如左子任务处理[left, mid]，右子任务处理[mid+1, right]，合并时仅操作[left, right]区间。

3. 确保子任务执行完毕再合并
   使用ExecutorService.invokeAll()等待所有子排序任务完成，或用CountDownLatch同步子线程状态，避免提前执行合并操作。

4. 检查索引计算逻辑
   排查合并过程中所有索引的计算（比如临时数组的索引、原数组的读写索引），避免出现数组越界（越界访问可能读取到内存中的垃圾值，比如Long.MIN_VALUE）或索引指向错误的情况。

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