Scala Ordering and Sorting, in depth: type classes, stable sorts, composition and the edge cases that bite

Ordering and Ordered: two ways to say what comes first

There are two traits, and they solve the same problem from opposite sides. Ordered[A] is something a type is: a class extends it and implements compare(that: A): Int, which gives it <, <=, > and >=. It extends java.lang.Comparable. Ordering[T] is something a type has: a separate value with compare(x: T, y: T): Int, defined outside the type, passed around as an implicit (a given in Scala 3). It extends java.util.Comparator[T] and PartialOrdering[T].

The contract for compare is the classic one: negative if the first argument comes first, zero if they are equivalent, positive otherwise. A valid ordering must be a total preorder: consistent (comparing the same pair twice gives the same sign), antisymmetric in sign (compare(a, b) and compare(b, a) have opposite signs) and transitive. The library never checks these properties. A sort given a broken comparator may return an arbitrary permutation or, because the underlying Java TimSort detects some violations, throw IllegalArgumentException: Comparison method violates its general contract!.

Prefer Ordering: a type has only one built-in Ordered order, but can have as many orderings as you need, including for types you do not own. The bridge between the two worlds is automatic: if a type is Ordered or Comparable, the standard library can derive an Ordering for it, and import scala.math.Ordered.orderingToOrdered gives infix operators to any type that has an Ordering.

How the compiler finds an Ordering

Methods that need an order take it as an implicit parameter: def sorted[B >: A](implicit ord: Ordering[B]). The compiler fills it in using the normal resolution rules our implicit resolution article walks through: first local and imported implicits, then the implicit scope of the type, which includes the companion object of Ordering itself and the companion of your type. That is why List(3, 1, 2).sorted works with no import: Ordering.Int lives in the Ordering companion.

The companion provides instances for primitives, String, BigInt, BigDecimal, Boolean (false before true), Unit, Option[T] and tuples up to arity nine, each built from orderings of its parts. Tuple orderings are lexicographic: compare the first element, and only on a tie look at the second. Option ordering puts None before every Some, and compares two Some values by their contents.

Collections are the awkward case. Sorting a List[List[Int]] can fall back on the implicit Ordering.Iterable, which is deprecated since 2.13.0 because iterables are not guaranteed to have a consistent order. The supported route is import scala.math.Ordering.Implicits.seqOrdering, which gives lexicographic order for any Seq. The same Ordering.Implicits object offers sortedSetOrdering and infixOrderingOps, which lets generic code write a < b for any T: Ordering.

Where to put your own instance matters. Define it in the companion object of the type it orders and every caller finds it with no import. Define a second, non-default ordering as a named value somewhere else and pass it explicitly. Never leave two candidates in scope at the same priority.

Building orderings from parts

You rarely implement compare by hand. The combinators cover almost every case and avoid the classic hand-written bug, returning a - b, which overflows for large ints and reverses the sign:

import scala.math.Ordering

final case class Employee(name: String, dept: String, salary: BigDecimal, hired: java.time.LocalDate)

object Employee {
  // Default order, found automatically: by department, then name.
  implicit val byDeptThenName: Ordering[Employee] =
    Ordering.by((e: Employee) => (e.dept, e.name))
}

// Alternative orders are named values, passed explicitly.
val bySalaryDesc: Ordering[Employee] =
  Ordering.by((e: Employee) => e.salary).reverse

// Chaining without allocating a tuple per comparison (2.13+).
implicit val localDateOrd: Ordering[java.time.LocalDate] =
  Ordering.fromLessThan(_ isBefore _)
val bySalaryDescThenSeniority: Ordering[Employee] =
  bySalaryDesc.orElseBy(_.hired)

// Scala 3 spelling of the default instance:
// object Employee:
//   given Ordering[Employee] = Ordering.by(e => (e.dept, e.name))

val staff: Vector[Employee] = loadStaff()
staff.sorted                       // uses Employee.byDeptThenName
staff.sorted(bySalaryDescThenSeniority)
staff.sortBy(_.name)(Ordering.String.reverse)
staff.maxByOption(_.salary)        // None on empty, unlike maxBy which throws

The building blocks are worth knowing by name. Ordering.by(f) orders by a derived key, and ord.on(f) is the same thing starting from an existing ordering. reverse flips it. orElse(other) and orElseBy(f) break ties: they call the second comparison only when the first returns zero, so they do not build a tuple on every comparison the way Ordering.by(e => (e.a, e.b)) does. Ordering.fromLessThan adapts a less-than function, and an anonymous new Ordering[T] { def compare(x: T, y: T) = ... } is the escape hatch for anything else. Because Ordering is a Comparator, you can pass it straight to Java APIs such as java.util.Collections.sort or a ConcurrentSkipListMap.

What sorted actually does

Knowing the implementation answers most performance and correctness questions. In 2.13, SeqOps.sorted copies the elements into an Array[Any], calls java.util.Arrays.sort on it with the ordering as the comparator, and appends the results to a builder for the original collection type. sortWith(lt) is literally sorted(Ordering.fromLessThan(lt)) and sortBy(f) is sorted(ord on f).

Three consequences follow. First, the sort is stable: elements the ordering considers equal keep their original relative order, which the documentation guarantees and which comes from Java's object sort being a TimSort merge sort. Stability is what makes multi-pass sorting work: sort by the secondary key, then stably by the primary key. Second, every sort is strict and copying: sorting a List of a million elements allocates an array of a million references and then a new list; sorting a view forces it. Third, sortBy evaluates the key function on every comparison, roughly 2 n log n times, not once per element. A key that parses a string or computes a hash is paid tens of millions of times on a large input.

Arrays take a separate path. arr.sorted on an Array[Int] with the default ordering sorts an unboxed copy, but a custom ordering, or an Array[Double], goes through boxed values. To skip both the copy and the boxing, java.util.Arrays.sort(arr) or scala.util.Sorting.quickSort(arr) sorts in place on unboxed values; the primitive overloads of quickSort delegate to java.util.Arrays.sort. The generic Sorting.quickSort[K: Ordering] sorts an array in place and is not stable; Sorting.stableSort is the stable alternative and also has overloads that take a Seq and return an array. The Scala arrays article covers the boxing rules in more depth.

Edge cases that change results

Doubles have two orders. IEEE 754 comparison is not a total order: NaN < x and NaN > x are both false, and -0.0 == 0.0. In 2.13 the default implicit Ordering[Double] is a total order with the semantics of java.lang.Double.compare: NaN sorts after every other value, -0.0 before 0.0, and lt, min and equiv now agree with compare. If you need IEEE behaviour from those methods, import Ordering.Double.IeeeOrdering; the sort order is the same either way. Check statistics code migrated from 2.12 that takes max or min around NaN.

Strings compare by UTF-16 code unit. Ordering.String uses compareTo, so all uppercase letters sort before lowercase ones, accented letters land after z, and digits compare character by character, which puts file10 before file9. For human-facing lists, use a java.text.Collator for the user's locale, and for strings containing numbers, split them and compare numerically, as the worked example below does.

Sorted collections use the ordering as their equality. TreeSet, TreeMap and SortedMap decide whether two elements are the same with compare == 0, not equals. Order employees by salary alone in a TreeSet and two people with the same salary become one element; the second insert is silently dropped. Any ordering used by a sorted collection must be consistent with equality, which in practice means ending the chain with a unique field such as an id.

Empty input throws. max, min, maxBy and minBy throw UnsupportedOperationException on empty collections. Use the Option-returning variants added in 2.13.

Worked example: ordering release versions

A deployment tool lists release tags and must pick the newest. The tags look like 1.9.2, 1.10.0, 1.10.0-rc.1 and 2.0.0-beta. Sorting them as strings gives 1.10.0 before 1.9.2 because the character 1 is less than 9, so the tool would deploy 1.9.2 as the latest. The fix is to model the version and give it an ordering that matches the meaning. The rules here follow the core of Semantic Versioning precedence: compare major, minor and patch numerically, and a pre-release sorts before the release with the same numbers. Full SemVer also compares dot-separated pre-release identifiers numerically where they are numeric; this simplified version compares the pre-release label as a string.

final case class Version(major: Int, minor: Int, patch: Int, pre: Option[String])

object Version {
  private val Pattern = raw"(\d+)\.(\d+)\.(\d+)(?:-([0-9A-Za-z.-]+))?".r

  def parse(s: String): Option[Version] = s match {
    case Pattern(a, b, c, pre) => Some(Version(a.toInt, b.toInt, c.toInt, Option(pre)))
    case _                     => None
  }

  // A release (pre = None) must sort AFTER its pre-releases, the opposite of
  // the standard Option ordering, so map it to (isRelease, label).
  private val preOrder: Ordering[Option[String]] =
    Ordering.by((p: Option[String]) => (p.isEmpty, p.getOrElse("")))

  implicit val ordering: Ordering[Version] =
    Ordering.by((v: Version) => (v.major, v.minor, v.patch))
      .orElse(preOrder.on((v: Version) => v.pre))
}

val tags = List("1.9.2", "1.10.0", "1.10.0-rc.1", "2.0.0-beta", "not-a-version")
val versions = tags.flatMap(Version.parse)
versions.sorted
// in order: 1.9.2, 1.10.0-rc.1, 1.10.0, 2.0.0-beta
versions.filter(_.pre.isEmpty).maxOption   // 1.10.0: the newest stable release

Three choices here generalise. The ordering lives in the companion, so every caller gets it for free. The awkward rule, that a missing pre-release label means newer, is isolated in one small named ordering instead of being buried in a hand-written compare. And parsing happens once, before sorting; if the code had used tags.sortBy(parse), the regular expression would run on every comparison. On half a million artifact paths that is the difference between milliseconds and seconds.

The same technique, sometimes called decorate-sort-undecorate, helps whenever the key is expensive: xs.map(x => (key(x), x)).sortBy(_._1).map(_._2) computes each key once. Because the sort is stable, equal keys keep their input order, so the result is the same as sortBy(key).

Top-k without sorting everything

Sorting everything to take the first ten is wasteful when the input is large or streaming. xs.sorted.take(k) costs O(n log n) time and O(n) extra memory. A bounded heap costs O(n log k) time and O(k) memory, and works on an iterator that never fits in memory:

import scala.collection.mutable

// Smallest k elements under `ord`, in ascending order, from any iterator.
def smallestK[A](it: Iterator[A], k: Int)(implicit ord: Ordering[A]): List[A] = {
  // PriorityQueue dequeues the LARGEST element under its ordering,
  // so the head is always the worst of the current best k.
  val heap = mutable.PriorityQueue.empty[A](ord)
  it.foreach { a =>
    if (heap.size < k) heap.enqueue(a)
    else if (ord.lt(a, heap.head)) { heap.dequeue(); heap.enqueue(a) }
  }
  heap.dequeueAll.reverse.toList
}

// Ten slowest requests from a log stream: "smallest" under the reversed order.
val slowest = smallestK(requests, 10)(Ordering.by((r: Request) => r.latencyMs).reverse)

Note that mutable.PriorityQueue is a max-heap under its ordering, the opposite of java.util.PriorityQueue; a unit test with a known answer catches a mix-up instantly.

Failure modes and trade-offs

The trade-offs are about where to pay. Tuple keys are readable but allocate per comparison; orElseBy chains do not. A type with several plausible orders is often better with no default at all. Sorting a primitive array in place is far cheaper than sorting boxed collections on hot paths, as our collections performance article discusses.

What to do next

1. Search your codebase for sortBy calls whose key does real work (parsing, regex, hashing, I/O) and precompute those keys once.
2. Find every TreeSet, TreeMap and SortedMap and confirm its ordering ends with a field that is unique per element.
3. Replace any hand-written compare that subtracts numbers with Ordering.by, orElse or Integer.compare.
4. Move each type's default ordering into its companion object, name every alternative ordering, and delete ad hoc local implicit orderings.
5. Check code that sorts or takes the max of Double values for NaN handling, and decide explicitly between the default total ordering and IeeeOrdering.
6. For user-visible lists of names, switch from Ordering.String to a locale-aware Collator ordering.
7. Write a property-based test (see our ScalaCheck article) asserting antisymmetry and transitivity for each custom ordering.