Dart中如何高效将已排序列表合并入另一个已排序列表？

两个输入列表本身已经按降序排列的前提下，有两种常用实现，性能差异明显：

• 最高效方案：双指针线性归并（时间复杂度O(m+n)）
  该方案完全利用了两个列表已有序的特性，不需要重复执行全量排序，是大数据量场景下的最优选择。

  List<int> messages = [10, 5, 4, 1];
  List<int> newMessages = [5, 3, 2];
  
  int ptrA = 0, ptrB = 0;
  final List<int> mergedResult = [];
  
  // 同步遍历两个列表，每次优先取更大的元素加入结果
  while (ptrA < messages.length && ptrB < newMessages.length) {
    if (messages[ptrA] >= newMessages[ptrB]) {
      mergedResult.add(messages[ptrA]);
      ptrA++;
    } else {
      mergedResult.add(newMessages[ptrB]);
      ptrB++;
    }
  }
  
  // 追加剩余未遍历完的元素
  if (ptrA < messages.length) {
    mergedResult.addAll(messages.sublist(ptrA));
  }
  if (ptrB < newMessages.length) {
    mergedResult.addAll(newMessages.sublist(ptrB));
  }
  
  messages = mergedResult;
  // 此时messages输出为 [10, 5, 5, 4, 3, 2, 1]，符合预期
  

• 简易写法（适合小数据量场景）
  如果列表长度普遍在百级以内，对性能要求不高，可以直接拼接后重排，代码更简洁：

  List<int> messages = [10, 5, 4, 1];
  List<int> newMessages = [5, 3, 2];
  
  messages.addAll(newMessages);
  // 传入降序比较规则完成排序
  messages.sort((a, b) => b.compareTo(a));
  

注意：如果列表元素量级达到万级以上，禁止使用拼接后重排的方案，O(n log n)的排序复杂度会带来明显的性能开销，优先选择双指针归并实现。

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