[Scala]why `scala.util.Sorting` is fast.

sorting_is_faster.md

scala.util.Sorting is faster than Seq#sorted

comparison for sorting Seq[Int] instance

scala.util.Sorting is faster for sorting primitive type sequence. The reason why scala.util.Sorting is fast is it select optimized sorting methods from java.util.Arrays. On the other hand, Seq#sorted using the same method from java.util.Arrays.

Seq#sorted

Inner Seq#sorted, using java.util.Arrays#sort. It's implementation is below.

public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        sort(a);
    } else {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            TimSort.sort(a, 0, a.length, c, null, 0, 0);
    }
}

scala.util.Sorting

Inner scala.util.Sorting, also using java.util.Arrays#sort. It's implementation is below.

public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

why scala.util.Sorting is faster?

Implementation of scala.util.Sorting#sort is below.

  @inline private def sort[T](a: Array[T], ord: Ordering[T]): Unit = a match {
    case _: Array[AnyRef]  => 
      // Note that runtime matches are covariant, so could actually be any Array[T] s.t. T is not primitive (even boxed value classes)
      if (a.length > 1 && (ord eq null)) throw new NullPointerException("Ordering")
      java.util.Arrays.sort(a, ord)
    case a: Array[Int]     => if (ord eq Ordering.Int) java.util.Arrays.sort(a) else mergeSort[Int](a, 0, a.length, ord)
    case a: Array[Double]  => mergeSort[Double](a, 0, a.length, ord)  // Because not all NaNs are identical, stability is meaningful!
    case a: Array[Long]    => if (ord eq Ordering.Long) java.util.Arrays.sort(a) else mergeSort[Long](a, 0, a.length, ord)
    case a: Array[Float]   => mergeSort[Float](a, 0, a.length, ord)   // Because not all NaNs are identical, stability is meaningful!
    case a: Array[Char]    => if (ord eq Ordering.Char) java.util.Arrays.sort(a) else mergeSort[Char](a, 0, a.length, ord)
    case a: Array[Byte]    => if (ord eq Ordering.Byte) java.util.Arrays.sort(a) else mergeSort[Byte](a, 0, a.length, ord)
    case a: Array[Short]   => if (ord eq Ordering.Short) java.util.Arrays.sort(a) else mergeSort[Short](a, 0, a.length, ord)
    case a: Array[Boolean] => if (ord eq Ordering.Boolean) booleanSort(a) else mergeSort[Boolean](a, 0, a.length, ord)
    // Array[Unit] is matched as an Array[AnyRef] due to covariance in runtime matching.  Not worth catching it as a special case.
    case null => throw new NullPointerException
  }

This implementation shows this is effective for only primitive-types. Therefore, Sorting is not effective for sorting my original type sequence.

Such sample scalamatsuri2017/SortOrSorting.scala at master · petitviolet/scalamatsuri2017