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

This is an excerpt from 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.

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