Scala: How to sort a sequence (Seq, List, Array, Vector)

Scala FAQ: How do I sort a mutable or immutable sequential collection in Scala, including Seq, List, Vector, Array, and ArrayBuffer?

(Also asked as, how do I implement the Ordered trait in a custom class so I can use the sorted method (or operators like <, <=, >, and >=) to compare instances of my class?

Solution

Before looking at how to sort other sequence types in Scala, it’s important to note that the preferred way to sort an Array is different than sorting the other sequential collections. If you want to sort an Array, see my other FAQ on How to sort an Array in Scala.

How to sort List, Vector, ArrayBuffer, and Seq

Now, if you want to sort a Scala sequence like a List, Vector, ArrayBuffer, Seq, and others, this article shows how to sort those with the sorted and sortWith methods (and the Ordered and Ordering traits).

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. (I discuss the Ordered trait more down below 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 object 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. To demonstrate this, first create a very basic class:

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

then 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
                        ^

This means that 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
    }

}

Now that the compare method provides the sorting capability, this new version of the Person class can be used with sorted. As shown in the comment, compare should work like this:

• Return 0 if the two objects are the same (i.e., they are “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.