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

Question

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

scala.collection.immutable.Vector.sorted

该文档说它是一种稳定的排序,但不是实际使用的算法.它是合并排序吗？

Answer 1

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

排序算法是一个经过调整的快速排序,改编自Jon L. Bentley和M. Douglas McIlroy的"工程排序功能",软件实践和经验,卷.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))性能,导致其他快速降序降级为二次性能,并且通常比传统(单枢轴)Quicksort实现更快.

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
  }

Answer 2

我广泛同意接受的答案.但是我想在Java 7阵列中添加一些要点

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

JAVA 7阵列排序与Primitives和不同Objects.

文件说明 -

对于原始值数组:

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

对于对象数组:

该实现改编自Tim Peters的Python排序(TimSort).它使用了Peter McIlroy的"乐观排序和信息理论复杂性"中的技术,参见"第四届年度ACM-SIAM离散算法研讨会论文集",第467-474页,1993年1月.

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. 

所以Java Arrays.sort应该使用TimSort !!!!!!

额外细节 -

你可以在这里找到JAVA7实现 - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

关于JAVA 7的更多精彩阅读 - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

这些更改对scala排序有影响,如此处所述 - http://grokbase.com/t/gg/scala-internals/12ab76zqnk/specializing-ordering-faster-sort