What algorithm is used by the Scala library method Vector.sorted?

scala, sorting, vector

Solution

The `sorted` method is implemented in `SeqLike`, and seems to use `java.util.Arrays.sort` for its sorting. It builds an array from the vector, then invokes `Arrays.sort` and then converts it back, it seems. According to the Java 6 documentation, it therefore uses quicksort:

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.

For Java 7, the algorithm seems to have change (again, citing 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's `SeqLike#sorted` source (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
  }

Problem

I have been looking at the Scala documentation but so far I have found no answer to my question, namely what sorting algorithm is used by the method ``` scala.collection.immutable.Vector.sorted ``` The documenation says it is a stable sort, but not the actual algorithm used. Is it a merge sort?

Original source