scala - Scala 库方法 Vector.sorted 使用什么算法？

Question

我一直在查看Scala 文档，但到目前为止我还没有找到我的问题的答案，即该方法使用什么排序算法

scala.collection.immutable.Vector.sorted

文档说这是一种稳定的排序，但不是实际使用的算法。是归并排序吗？

score 16 · Accepted Answer

该sorted方法在中实现SeqLike，并且似乎java.util.Arrays.sort用于其排序。它从向量构建一个数组，然后调用Arrays.sort然后将其转换回来，看起来。根据Java 6 文档，它因此使用快速排序：

排序算法是一种调整过的快速排序，改编自 Jon L. Bentley 和 M. Douglas McIlroy 的“Engineering a Sort Function”，Software-Practice and Experience，Vol。23(11) P. 1249-1265（1993 年 11 月）。该算法在许多数据集上提供 n*log(n) 性能，导致其他快速排序降低到二次性能。

对于 Java 7，算法似乎发生了变化（再次引用文档）：

排序算法是 Vladimir Yaroslavskiy、Jon Bentley 和 Joshua Bloch 的 Dual-Pivot Quicksort。该算法在许多数据集上提供 O(n log(n)) 性能，导致其他快速排序降低到二次性能，并且通常比传统的（单轴）快速排序实现更快。

Scala 的SeqLike#sorted源代码（取自 GitHub）：

/** Sorts this $coll according to an Ordering.
   *
   *  The sort is stable. That is, elements that are equal (as determined by
   *  `lt`) appear in the same order in the sorted sequence as in the original.
   *
   *  @see [[scala.math.Ordering]]
   *
   *  @param  ord the ordering to be used to compare elements.
   *  @return     a $coll consisting of the elements of this $coll
   *              sorted according to the ordering `ord`.
   */
  def sorted[B >: A](implicit ord: Ordering[B]): Repr = {
    val len = this.length
    val arr = new ArraySeq[A](len)
    var i = 0
    for (x <- this.seq) {
      arr(i) = x
      i += 1
    }
    java.util.Arrays.sort(arr.array, ord.asInstanceOf[Ordering[Object]])
    val b = newBuilder
    b.sizeHint(len)
    for (x <- arr) b += x
    b.result
  }

score 10 · Accepted Answer

我广泛同意接受的答案。但是我想在Java 7 数组中添加一些要点

答案会稍微改变自JAVA 7以来带来的变化，它使用 QuickSort 的变体对java.util.Arrays 中的原始值DualPivotQuickSort进行排序

JAVA 7 数组排序对于Primitives和是不同的Objects。

来自文档的注释 -

对于原始值数组：

排序算法是Vladimir Yaroslavskiy、Jon Bentley 和 Joshua Bloch的Dual-Pivot Quicksort 。该算法在许多数据集上提供 O(n log(n)) 性能，导致其他快速排序降低到二次性能，并且通常比传统的（单轴）快速排序实现更快。

对于对象数组：

该实现改编自 Tim Peters 的 Python 列表排序 ( TimSort )。它使用了 Peter McIlroy 在 1993 年 1 月的第四届 ACM-SIAM 离散算法研讨会论文集上的“乐观排序和信息理论复杂性”中的技术。

SeqLike.sorted uses 
java.util.Arrays.sort(arr.array, ord.asInstanceOf[Ordering[Object]]) 
where arr.array is instead of ArraySeq.

ArraySeq in Scala stores its data in a plain old Java array, 
but it does not store arrays of primitives; everything is an array of objects. 
This means that primitives get boxed on the way in.