Scala List排序与Python列表排序执行时间对比及性能差异疑问

核心原因在于两者的数据结构和排序实现的本质差异： #

• 数据结构不同：链表 vs 动态数组
  Scala的List是不可变单链表，这种结构天生不适合排序操作——排序需要频繁访问元素，链表的随机访问时间复杂度是O(n)，而且排序时必须先把链表转换成数组（这一步就有O(n)的时间和空间开销），再进行排序，最后还要转回链表。而Python的list是动态数组，内存连续存储，缓存命中率高，排序时直接在数组上操作，没有额外的结构转换成本。

• 排序底层实现的性能差距
  Python的sorted()用的是C实现的Timsort算法，这是一种高度优化的混合排序算法，专门针对数组结构做了大量优化，性能拉满。而Scala的List.sorted底层依赖Java的排序实现，但因为要先把链表转数组，这个转换的开销在百万级数据下会被放大，抵消了JVM的性能优势。

• 测试代码的潜在偏差

  • JVM预热问题：Scala运行在JVM上，第一次运行时JIT编译器还没完成代码优化，多次运行后性能会明显提升；而Python的排序逻辑是C实现的，第一次运行就接近最优性能。如果只测单次运行，Scala的结果会偏慢。
  • 换用Scala的数组类型性能会反转：如果把Scala代码里的List换成Array或Vector，排序性能会追上甚至超过Python。比如用Array测试：

    import scala.util.Random
    
    @main
    def Main(args: String*): Unit =
      def cmillis = System.currentTimeMillis()
      val n = 1_000_000
    
      val xs = Array.fill(n)(Random.nextInt(n))
      val currentMillis = cmillis
      scala.util.Sorting.quickSort(xs)
      println("Sorted in " + (cmillis - currentMillis) + "ms")
    

• 不可变结构的额外开销
  Scala的List是完全不可变的，排序过程中无法修改原链表，必须创建新的节点来构建排序后的链表，这会产生大量对象创建和内存分配的开销；而Python的sorted()虽然也返回新列表，但底层数组操作是高效的内存块处理，开销远低于链表的节点创建。

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