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

Question

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

scala.collection.immutable.Vector.sorted

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

Answer 1

sorted 方法是在 SeqLike 中实现的，并且似乎使用 java.util.Arrays.sort 进行排序。它似乎从向量构建一个数组，然后调用 Arrays.sort ，然后将其转换回来。根据Java 6 documentation ，因此它使用快速排序:

The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

对于 Java 7，算法似乎发生了变化(再次引用 the docs ):

The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

Scala 的 SeqLike#sorted 源 (taken from 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
  }