How to sort Scala collections classes (sortWith, sorted, Ordered, Ordering)

This is an excerpt from the 1st Edition of the Scala Cookbook (partially modified for the internet). This is Recipe 10.28, “How to Sort a Scala Collection.”

Problem

You want to sort a sequential collection. Or, you want to implement the Ordered trait in a custom class so you can use the sorted method, or operators like <, <=, >, and >= to compare instances of your class.

Solution

See Recipe 11.10, “Sorting Arrays”, for information on how to sort an Array. Otherwise, use the sorted or sortWith methods to sort a collection.

The sorted method can sort collections with type Double, Float, Int, and any other type that has an implicit scala.math.Ordering:

scala> val a = List(10, 5, 8, 1, 7).sorted
a: List[Int] = List(1, 5, 7, 8, 10)

scala> val b = List("banana", "pear", "apple", "orange").sorted
b: List[String] = List(apple, banana, orange, pear)

The “rich” versions of the numeric classes (like RichInt) and the StringOps class all extend the Ordered trait, so they can be used with the sorted method. (More on the Ordered trait in the Discussion.)

The sortWith method lets you provide your own sorting function. The following examples demonstrate how to sort a collection of Int or String in both directions:

scala> List(10, 5, 8, 1, 7).sortWith(_ < _)
res1: List[Int] = List(1, 5, 7, 8, 10)

scala> List(10, 5, 8, 1, 7).sortWith(_ > _)
res2: List[Int] = List(10, 8, 7, 5, 1)

scala> List("banana", "pear", "apple", "orange").sortWith(_ < _)
res3: List[java.lang.String] = List(apple, banana, orange, pear)

scala> List("banana", "pear", "apple", "orange").sortWith(_ > _)
res4: List[java.lang.String] = List(pear, orange, banana, apple)

Your sorting function can be as complicated as it needs to be. For example, you can access methods on the elements during the sort, such as the following example, which sorts a list of strings by the string length:

scala> List("banana", "pear", "apple", "orange").sortWith(_.length < _.length)
res5: List[java.lang.String] = List(pear, apple, banana, orange)

scala> List("banana", "pear", "apple", "orange").sortWith(_.length > _.length)
res6: List[java.lang.String] = List(banana, orange, apple, pear)

In the same way the length method is called on a String, you can call a method on any class you want to sort. If your sorting method gets longer, first declare it as a method:

def sortByLength(s1: String, s2: String) = {
    println("comparing %s and %s".format(s1, s2))
    s1.length > s2.length
}

Then use it by passing it into the sortWith method:

scala> List("banana", "pear", "apple").sortWith(sortByLength)
comparing banana and pear
comparing pear and apple
comparing apple and pear
comparing banana and apple
res0: List[String] = List(banana, apple, pear)

Discussion

If the type a sequence is holding doesn’t have an implicit Ordering, you won’t be able to sort it with sorted. For instance, given this basic class:

class Person (var name: String) {
    override def toString = name
}

create a List[Person]:

val ty = new Person("Tyler")
val al = new Person("Al")
val paul = new Person("Paul")
val dudes = List(ty, al, paul)

If you try to sort this list in the REPL, you’ll see an error stating that the Person class doesn’t have an implicit Ordering:

scala> dudes.sorted
<console>:13: error: No implicit Ordering defined for Person.
              dudes.sorted
                    ^

You can’t use sorted with the Person class as it’s written, but you can write a simple anonymous function to sort the Person elements by the name field using sortWith:

scala> val sortedDudes = dudes.sortWith(_.name < _.name)
sortedDudes: Array[Person] = Array(Al, Paul, Tyler)

scala> val sortedDudes = dudes.sortWith(_.name > _.name)
sortedDudes: Array[Person] = Array(Tyler, Paul, Al)

Mix in the Ordered trait

If you’d rather use the Person class with the sorted method, just mix the Ordered trait into the Person class, and implement a compare method. This technique is shown in the following code:

class Person (var name: String) extends Ordered [Person] {
    override def toString = name

    // return 0 if the same, negative if this < that, positive if this > that
    def compare (that: Person) = {
        if (this.name == that.name)
            0
        else if (this.name > that.name)
            1
        else
            −1
    }
}

This new Person class can be used with sorted. The compare method is what provides the sorting capability. As shown in the comment, compare should work like this:

• Return 0 if the two objects are the same (equal, typically using the equals method of your class)
• Return a negative value if this is less than that
• Return a positive value if this is greater than that

How you determine whether one instance is greater than another instance is entirely up to your compare algorithm.

Note that because this compare algorithm only compares two String values, it could have been written like this:

def compare (that: Person) = this.name.compare(that.name)

However, I wrote it as shown in the first example to be clear about the approach.

An added benefit of mixing the Ordered trait into your class is that it also lets you compare object instances directly in your code:

if (al > ty) println("Al") else println("Tyler")

This works because the Ordered trait implements the <=, <, >, and >= methods, and calls your compare method to make those comparisons.

See Also

For more information, the Ordered and Ordering Scaladoc is excellent, with good examples of this approach, and other approaches.

• The Ordering trait
• The Ordered trait