scala - Scala ライブラリ メソッド Vector.sorted で使用されるアルゴリズムは何ですか?

Question

私はScalaのドキュメントを見てきましたが、これまでのところ、私の質問に対する答えは見つかりませんでした。つまり、メソッドで使用されているソートアルゴリズムは何ですか?

scala.collection.immutable.Vector.sorted

ドキュメントには、安定したソートであると書かれていますが、実際に使用されているアルゴリズムではありません。マージソートですか？

Answer 1

このsortedメソッドはで実装されており、その並べ替えSeqLikeに使用されているようです。java.util.Arrays.sortベクトルから配列を作成し、それを呼び出しArrays.sortてから元に戻すようです。したがって、Java 6のドキュメントによると、クイックソートを使用しています。

ソートアルゴリズムは、JonL.BentleyとM.DouglasMcIlroyの「EngineeringaSortFunction」、Software-Practice and Experience、Vol。23（11）P. 1249-1265（1993年11月）。このアルゴリズムは、多くのデータセットでn * log（n）のパフォーマンスを提供し、他のクイックソートのパフォーマンスを2次パフォーマンスに低下させます。

Java 7の場合、アルゴリズムに変更が加えられているようです（ここでも、ドキュメントを引用しています）。

並べ替えアルゴリズムは、Vladimir Yaroslavskiy、Jon Bentley、およびJoshuaBlochによるデュアルピボットクイックソートです。このアルゴリズムは、多くのデータセットでO（n log（n））パフォーマンスを提供し、他のクイックソートのパフォーマンスを2次パフォーマンスに低下させます。通常、従来の（1ピボット）クイックソート実装よりも高速です。

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
  }