什么算法使用Scala库方法Vector.sorted？(What algorithm is use

我一直在寻找的斯卡拉文档，但到目前为止，我没有发现任何回答我的问题，即所使用的方法是什么排序算法

scala.collection.immutable.Vector.sorted

该documenation说，这是一个稳定的排序，而不是实际使用的算法。它是一个合并排序？

Answer 1:

该sorted方法在实施SeqLike ，并似乎用java.util.Arrays.sort其排序。它建立从向量的阵列，然后调用Arrays.sort然后将其转换回，它似乎。按照Java 6的文档，因此它使用了快速排序 ：

该排序算法是一种调整快速排序，改编自乔恩L.宾利和M.道格拉斯麦克罗伊的“工程排序功能”，软件实践与经验，卷。 23（11）1249年至1265年P.（1993年11月）。该算法提供了许多数据集，导致其他快速排序会降低二次型性能的n * log（n）性能。

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

该排序算法是一个双枢轴快速排序弗拉基米尔·Yaroslavskiy，乔恩·本特利，以及约书亚·布洛克。该算法提供了许多数据集，导致其他快速排序会降低二次型性能O（N日志（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
  }

Answer 2:

我接受的答案大致同意。但是我想补充几点WRT Java 7个的数组

答案将略有变化WRT到使用所谓的快速排序的变化，因为JAVA 7所带来的变化DualPivotQuickSort在java.util.Arrays中的 原始值进行排序

JAVA 7数组排序为不同Primitives和Objects 。

从文档注意 -

对于原始值数组：

该排序算法是一个双枢轴快速排序弗拉基米尔·Yaroslavskiy，乔恩·本特利，以及约书亚·布洛克。 该算法提供了许多数据集，导致其他快速排序会降低二次型性能O（N日志（n））的性能，并且通常速度比传统的（一个支点）快速排序的实现。

对于对象数组：

实现改编自蒂姆·彼得斯的列表排序的Python（TimSort）。 它使用从彼得麦克罗伊的“乐观排序和信息理论的复杂性”，在第四次年度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.