How to use Scala’s sortInPlaceBy method on mutable sequences (ArrayBuffer, ArrayDeque)

When I first looked at the sortInPlaceBy method that was introduced on mutable sequences in Scala 2.13, I couldn’t figure out exactly what it was supposed to do.

Unable to find any examples of “scala sortInPlaceBy” on planet Earth this evening (February 23, 2020), I had to resort to some actual work, and looked at the Scaladoc.

Reading the Scaladoc

This is what I see when I look at the Scaladoc for sortInPlaceBy on the ArrayBuffer:

def sortInPlaceBy[B](f: (A) => B)(implicit ord: Ordering[B]): ArrayBuffer.this.type

You can’t see by looking at that method what A is, so I scrolled up to the top of the page and saw this at the beginning of the Scaladoc:

class ArrayBuffer[A] extends ...

Having seen that, I can now read the sortInPlaceBy Scaladoc:

  • Given two generic types A and B,
  • Where A is the type contained in the list, such as A being an Int when you have a List[Int],
  • sortInPlaceBy takes a function that transforms an A to a B, and
  • The type B must have an implicit Ordering, or else you need to provide an explicit Ordering for it

How I think sortInPlaceBy works

What you can’t tell by looking at the sortInPlaceBy method signature is that it feels like it creates a sequence that temporarily exists in parallel to your initial sequence, and it uses the sorting in that sequence to re-order the elements in the ArrayBuffer. I haven’t looked into the source code to see whether or not that’s exactly how it works, but as you’ll see in the following examples, it feels like it works that way.

(Also, I don’t have a degree in computer science and didn’t study algorithms while getting my aerospace engineering degree, so it may work some other way.)

A sortInPlaceBy example

Given that background, let’s look at an example of how sortInPlaceBy works. Given this ArrayBuffer:

import scala.collection.mutable.ArrayBuffer
val a = ArrayBuffer("apple", "kiwi", "fig", "banana")

you can write a function that transforms an A — the String type in the ArrayBuffer — to a type B. This function will be used to create my theoretical Seq[B] that exists in parallel to a, and once it’s created, it will be used to re-order the elements in a. For example, here’s a function that can be used to sort the strings by their length:

def sortByStringLength(s: String): Int = s.length

Now when you call sortInPlaceBy with sortByStringLength, you see this result:

scala> a.sortInPlaceBy(sortByStringLength)
// a: ArrayBuffer(fig, kiwi, apple, banana)

As I hoped for, the strings are now sorted in a according to their string length.

Note that giving that function the name sortByStringLength is a little overkill. Since it just returns the string length, I could have just called it stringLength, stringLen, or just used an anonymous function:

a.sortInPlaceBy(_.length)

A second example

Without much discussion, here’s another example that shows how to use sortInPlaceBy, this time using a Person class and ArrayBuffer:

class Person(var firstName: String, var lastName: String)
    override def toString = s"$firstName $lastName".trim

val a = ArrayBuffer(
    Person("Jessica", "Day"),
    Person("Winston", "Bishop"),
    Person("Coach", ""),
    Person("Nick", "Miller"),
    Person("", "Schmidt")
)

def sortByFirstNameLength(p: Person): Int = p.firstName.length

a.sortInPlaceBy(sortByFirstNameLength)

After that last line the contents of a are:

ArrayBuffer(Schmidt, Nick Miller, Coach, Jessica Day, Winston Bishop)

While this example still relies on the string length for sorting, it’s at least a little more complicated, and more of a real-world example.

Discussion

While it was hard to initially grok sortInPlaceBy, these examples are relatively simple, especially because I keep the type B simple — it’s just an Int in both examples. For more complicated sorting situations you can make your type B as complicated as it needs to be, as long as that type supports an implicit ordering or you can provide it explicitly.

When you need to sort a mutable sequence in place you can also use these methods, which I found to be easier to understand at first glance:

  • sortInPlace
  • sortInPlaceWith

Between these three methods, they give you some sorting power mojo. Remember that there are other ways to sort immutable sequences, and you can also sort a plain old Scala Array with scala.util.Sorting.quickSort.

... this post is sponsored by my books ...
 

Summary

In summary, if you wanted/needed to see an example how to use sortInPlaceBy on a mutable Scala sequence, I hope these examples are helpful.