A Guide to Sorting in Scala

1. Overview

Sorting is arranging a data set in ascending or descending order based on criteria.

It’s very important for making search easy and effective. We use it every day to find a wanted phone number or the cheapest product on a website.

In our previous tutorials, we took a look at sorting in Java. Today, we’ll show different options for sorting sequences in Scala.

2. Example

In the following examples, we’ll sort a list of users. Each has a name and age:

case class User(name: String, age: Int)

val users = List(
  User("Mike", 43),
  User("Mike", 16),
  User("Kelly", 21)
)

3. sorted

There’s a dedicated sorted method that sorts items in a sequence according to an Ordering instance:

def sorted[B >: A](implicit ord: Ordering[B]): Repr

Repr is the type of the actual collection containing elements; in our case, it’s a List. A is the type of element in the collection; in our case, it’s a User.

Let’s try to sort users:

users.sorted

Actually, It’ll not compile since no implicit Ordering was defined for the User. To make compiler happy, we need to provide the missing implicit parameter:

implicit val userOrdering: Ordering[User] = Ordering.by(_.age)

users.sorted shouldBe List(
  User("Mike", 16),
  User("Kelly", 21),
  User("Mike", 43)
)

Right now compiler knows that we want to order users by age. If we want to have reverse ordering then we can use the reverse method on Ordering:

implicit val userOrdering: Ordering[User] = Ordering.by[User, Int](_.age).reverse

users.sorted shouldBe List(
  User("Mike", 43),
  User("Kelly", 21),
  User("Mike", 16)
)

Another way of making sorted compile would be making User inherit from the Ordered[User]:

case class User(name: String, age: Int) extends Ordered[User] {
    override def compare(that: User): Int =
      java.lang.Integer.compare(age, that.age)
}

users.sorted shouldBe List(
  User("Mike", 16),
  User("Kelly", 21),
  User("Mike", 43)
)

We may ask ourselves, how the compiler can find Ordering for User in scope. It works because there is an implicit conversion method available in scope. This method can return Ordering for any type which extends java.lang.Comparable:

implicit def ordered[A <% Comparable[A]]: Ordering[A] = new Ordering[A] {
    def compare(x: A, y: A): Int = x compareTo y
}

So, since there’s no implicit Ordering for User, the compiler will convert Ordered[User] into Ordering[User].

An attentive reader will notice that the implicit conversion method requires Comparable not Ordered. Correct! But, it’s working without problems because Ordered extends Comparable:

trait Ordered[A] extends Any with java.lang.Comparable[A]

4. sortBy

If we want to sort our data by a particular field, we can use the sortBy method as long there is an Ordering field type in scope:

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

Let’s sort users by name:

users.sortBy(_.name) shouldBe List(
  User("Kelly", 21),
  User("Mike", 43),
  User("Mike", 16)
)

We may ask if we didn’t forget to define Ordering[String] in scope. We don’t need to define it, because Scala has predefined Ordering for all data types such as Char, Int, String, and Boolean.

There’s also predefined Ordering for Tuple, which gives us the possibility to order data by multiple fields. Let use it to sort users by name and age:

users.sortBy(u => (u.name, u.age)) shouldBe List(
  User("Kelly", 21),
  User("Mike", 16),
  User("Mike", 43)
)

5. sortWith

If we want to forget about Ordering, we can use the sortWith method, which sorts elements according to the given comparison function:

def sortWith(lt: (A, A) => Boolean): Repr

Let’s now sort users from the oldest to the youngest:

users.sortWith(_.age > _.age) shouldBe List(
  User("Mike", 43),
  User("Kelly", 21),
  User("Mike", 16)
)

6. Conclusion

In this short tutorial, we reviewed three different methods for sorting data in Scala. We also learned about Ordering, which represents a strategy for sorting.