Android与Oracle JDK的TimSort排序子数组时是否存在内存浪费？

现象确认与版本区分 #

首先需要明确：在主流Oracle JDK 8+版本和现代Android SDK（API 26+）中，TimSort处理数组子范围排序时，合并用临时数组的容量是子范围长度的一半，而非整个数组的一半。如果您观察到临时数组为整个数组一半的情况，大概率是旧版本实现的疏漏，或是测试场景中存在特殊条件（比如子范围长度接近整个数组长度）。

核心疑问解答 #

1. 该行为是有意设计还是实现疏漏？ #

• 主流版本：有意的权衡设计
  TimSort的合并逻辑中，最多需要临时存储两个待合并run段中较小的那个的所有元素。根据TimSort的run合并策略，待合并的两个run段中，较小段的长度不会超过当前排序范围总长度的一半。因此，将临时数组大小设为排序范围长度的一半，既能满足合并需求，又能避免频繁的内存分配与释放，是性能与内存占用的平衡选择。
• 旧版本：实现疏漏
  在早期的Android（如API 26之前）和部分旧版Oracle JDK中，存在处理子范围排序时错误使用整个数组长度计算临时数组大小的情况，这属于实现层面的疏漏，并非设计意图。

2. 是否有其他人发现此问题？ #

是的，这类内存浪费问题曾在社区被多次反馈：

• Android的AOSP仓库中曾收到相关issue，后续版本已修复该问题；
• Oracle JDK的Bug数据库中也有类似报告，对应的修复已纳入后续更新版本。

3. 能否针对该场景优化临时数组大小？ #

根据使用的版本不同，优化方式分为两种：

• 使用新版本（推荐）：直接升级到JDK 8+或Android API 26+，官方实现已自动根据子范围长度调整临时数组大小，无需额外操作。
• 兼容旧版本：手动创建容量为(hi - lo) >>> 1的临时数组，调用Arrays.sort的重载方法：

  Arrays.sort(a, lo, hi, comparator, tempArray, 0, tempArray.length);
  

  以此替代默认的子范围排序方法，避免不必要的内存浪费。

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