Is scala sorting stable?

Question

Scala collections have sortBy method. Is that method stable?

def sortList(source : List[Int]) : List[Int] =
  source.sortBy(_ % 2)

Would that example always preserve order?

Answer 1

Yes, it's stable. Reference from scala source code:

https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/SeqLike.scala#L627

def sortBy[B](f: A => B)(implicit ord: Ordering[B]): Repr = sorted(ord on f)

/** 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 b = newBuilder
  if (len == 1) b ++= this
  else if (len > 1) {
    b.sizeHint(len)
    val arr = new Array[AnyRef](len)  // Previously used ArraySeq for more compact but slower code
    var i = 0
    for (x <- this) {
      arr(i) = x.asInstanceOf[AnyRef]
      i += 1
    }
    java.util.Arrays.sort(arr, ord.asInstanceOf[Ordering[Object]])
    i = 0
    while (i < arr.length) {
      b += arr(i).asInstanceOf[A]
      i += 1
    }
  }
  b.result()
}