Arrays.sort是使用什么排序算法实现的？
面试被问到 Arrays.sort 的实现，我一般不会只蹦出“快排”两个字。它背后是一整套分情况、分版本、分数据特征的组合拳——理解这套思路，比死记名字有用得多。
🔍 先抓主线：Java 按“数据类型”选不同的算法¶
Arrays.sort() 重载了一堆方法，核心分两派：
-
原始类型（
int[]、long[]、double[]等）→ Dual-Pivot QuickSort -
对象类型（
Object[]、String[]等）→ TimSort
这个分界线从 Java 7 开始确立。之前原始类型用传统的单轴快排，对象用归并排序。
⚡ 原始类型：Dual-Pivot QuickSort（双轴快速排序）¶
🎯 为什么用双轴快排？¶
-
更快：比传统单轴快排比较次数更少，尤其在大量重复元素时优势明显。
-
不要求稳定性：数字排序只关心大小，
3和另一个3谁前谁后没有语义，所以可以牺牲稳定性换性能。
📊 实现逻辑¶
- 选两个轴（P1、P2，P1 ≤ P2），把数组分成三区：
-
递归对三块区域继续排序。
-
小数组切换插入排序：当子数组长度小于某个阈值（如 47），改用插入排序，减少递归开销。
-
处理特殊值：对于
float/double，把所有 NaN 都“挤”到数组末尾，保证排序一致性。
🧠 一句话概括¶
用“两个轴”减少比较，用“插入排序”兜底小数组，用“不稳定性”换取极致吞吐。
🧩 对象类型：TimSort（蒂姆排序）¶
🎯 为什么对象必须用 TimSort？¶
-
稳定性是刚需：对象可能已经按某个字段排过序，如果第二次排序不稳定，会打乱原有顺序。比如先按年龄排，再按部门排，稳定排序能保留同部门内年龄顺序。
-
利用部分有序性：现实数据往往局部有序（如日志时间戳），TimSort 能识别这些连续递增段（run），大幅减少归并次数。
📐 TimSort 的工作原理¶
-
扫描数组，找出自然 run（连续升序或严格降序的段），降序段反转成升序。
-
短 run 用二分插入排序扩展到最小长度（如 32），保证每个 run 长度达标。
-
用归并策略合并这些 run，合并时使用“暂存空间 + 跳跃式归并”优化，尽可能平衡栈和内存。
本质上，TimSort 是 “自适应归并排序 + 插入排序” 的合体，专门讨好真实世界的数据分布。
⚖️ 为什么不让原始类型也用 TimSort？¶
正是因为对象排序有“保序”的契约，Java 才不敢用不稳定的快排，否则会破坏
Comparator的约定。
🛠️ 一个常被追问的细节：parallelSort 怎么做？¶
Arrays.parallelSort() 内部用 Fork-Join 框架并行化：
-
将数组切块，每个线程独立排序（原始类型用双轴快排，对象用 TimSort）。
-
最后多路归并。
-
适合 大数组（> 8192） 且多核环境，小数组反而会有调度开销。
Arrays.sort 给每种数据都挑了最合身的“衣服”——原始类型穿轻便运动装（双轴快排），对象类型穿正式西装（TimSort）。
面试时能说出 “它不仅是排序，是对数据类型语义的尊重”，面试官就知道你不只背过 API，而是琢磨过 Java 库设计的取舍智慧。