好未来需要按学生成绩排名，要求稳定排序（相同成绩的学生顺序不变），且支持大规模数据（如百万级学生）。请设计一个排序算法，说明时间复杂度，并解释如何处理成绩相同的情况。

1) 【一句话结论】：采用归并排序（Merge Sort），它通过分治策略实现稳定排序，时间复杂度O(nlogn)，空间复杂度O(n)，适合大规模数据，且能保证相同成绩的学生顺序不变。

2) 【原理/概念讲解】：归并排序是典型的分治算法，核心思想是将待排序数组不断拆分成更小的子数组，直到子数组长度为1（有序），然后合并这些有序子数组，得到最终有序序列。合并时，比较两个有序子数组的当前元素，选择较小的放入结果数组；若两个元素相等，优先放入左子数组的元素（因为左子数组是之前排序的左半部分，顺序不变），这样保证了排序的稳定性。比如，合并[85, 92]和[85, 78]，合并后是[85, 85, 78, 92]，其中两个85的顺序与原左子数组一致，保持稳定性。

3) 【对比与适用场景】：

排序算法	定义	时间复杂度	稳定性	使用场景	注意点
归并排序	分治法，拆分-合并	O(nlogn)（所有情况）	稳定	大规模数据，需要稳定排序	需要额外O(n)空间
快速排序	分治法，基于分区	O(nlogn)（平均），O(n²)（最坏）	不稳定	大规模数据，通常更快	最坏情况不稳定
堆排序	堆数据结构，选择排序	O(nlogn)	不稳定	大规模数据，原地排序	不稳定，时间复杂度稳定

4) 【示例】：
假设学生数据结构为 Student，包含 id（唯一标识）和 score（成绩），待排序数组 students = [{id:1,score:85}, {id:2,score:92}, {id:3,score:85}, {id:4,score:78}]。

• 分治过程：将数组分成两半，分别排序后合并。
• 合并时，比较 score，若相等则优先放左子数组的元素（如 id=1 的85在 id=3 之前），最终排序结果为 [ {id:1,score:85}, {id:2,score:92}, {id:3,score:85}, {id:4,score:78} ]（按score升序，相同score保持原顺序）。

5) 【面试口播版答案】：
“需要稳定排序且处理大规模数据，我会选择归并排序。归并排序通过分治策略，将数组拆分成更小的子数组，分别排序后合并，合并时若元素相等，优先放左子数组的元素（保证原顺序），实现稳定排序。时间复杂度是O(nlogn)，适合百万级数据，空间复杂度O(n)，能高效处理大规模数据，满足相同成绩顺序不变的要求。”

6) 【追问清单】：

• 问题1：为什么不用快速排序？
  回答要点：快速排序是分治法但基于分区，最坏情况下不稳定（相同成绩顺序可能改变），且时间复杂度最坏为O(n²)，不适合大规模数据。
• 问题2：如果成绩范围很大（如0-10亿），归并排序是否合适？
  回答要点：归并排序时间复杂度O(nlogn)稳定，但空间复杂度O(n)可能占用较多内存。若内存有限，可考虑基数排序（时间O(nk)，k为位数），但需假设成绩为整数且范围有限。
• 问题3：合并过程中如何保证稳定性？
  回答要点：合并时比较两个有序子数组的当前元素，相等时优先放入左子数组的元素（左子数组是原左半部分，顺序不变），确保相同成绩的学生顺序与原数组一致。
• 问题4：百万级数据时，递归深度是否会导致栈溢出？
  回答要点：递归深度为log₂n，百万级数据约20层，远小于栈限制，不会导致栈溢出。
• 问题5：归并排序是否可以原地排序？
  回答要点：传统归并排序需要额外空间，但可优化为原地归并（如自底向上合并），空间复杂度可降为O(1)，但时间复杂度仍为O(nlogn)。

7) 【常见坑/雷区】：

• 1. 忽略稳定性，误用快速排序或堆排序；
• 2. 时间复杂度分析错误，如认为归并排序空间复杂度O(1)；
• 3. 合并时处理相等元素的方式错误，导致不稳定；
• 4. 忽略大规模数据的空间需求，未说明额外空间；
• 5. 分治过程中递归深度导致栈溢出的风险未提及（虽百万级数据不影响，但需说明）。