In a production environment, you'll almost never write your own sorting algorithm. You'll use .sorted or .sortBy and call it a day. But if you're aiming for senior-level fluency in Scala, you need to understand how these algorithms map to the language's strengths—specifically the tension between imperative mutation and functional purity.

To keep this concrete, let's build a small inventory management tool. We aren't just sorting integers; we're sorting Product objects. This makes things interesting because we have to deal with Ordering and stability.

Defining our Product Domain

First, let's define what we're actually sorting. I'm using a case class here because it gives us equals and hashCode for free, which is helpful when we start verifying our sorts.

case class Product(name: String, price: Double)

Tackling the Bubble Sort (and a common stumble)

I want to start with Bubble Sort. It's inefficient, sure, but it's the classic way to think about "swapping" elements. I'll try to implement this using a standard List first, because that's what we use 90% of the time in Scala.

def bubbleSort(items: List[Product]): List[Product] = {
  val n = items.length
  for (i <- 0 until n) {
    for (j <- 0 until n - i - 1) {
      if (items(j).price > items(j + 1).price) {
        // I'm trying to swap them here
        items(j) = items(j + 1) 
        items(j + 1) = items(j)
      }
    }
  }
  items
}

Wait. If you try to compile that, the compiler is going to scream at you. I did this a dozen times when I was transitioning from Java to Scala. I tried to treat a List like an array. In Scala, List is an immutable linked list. You can't assign a value to an index. Even if I used a while loop, the List(j) access is O(n), making this algorithm O(n³). That's a disaster.

To fix this and keep the "swapping" logic, I need to use an Array, which is mutable and provides O(1) random access.

def bubbleSortFixed(items: List[Product]): List[Product] = {
  val arr = items.toArray
  val n = arr.length
  for (i <- 0 until n) {
    for (j <- 0 until n - i - 1) {
      if (arr(j).price > arr(j + 1).price) {
        val temp = arr(j)
        arr(j) = arr(j + 1)
        arr(j + 1) = temp
      }
    }
  }
  arr.toList
}

Quick Sort with Pattern Matching

Now, let's move away from that imperative style. This is where Scala really shines. Quick Sort is naturally recursive, and when you combine that with pattern matching and filters, the code becomes almost a mathematical definition.

I'm going to use the first element as the pivot. In a real-world scenario, you'd pick a random pivot to avoid O(n²) worst-case performance on already-sorted lists, but for this example, the clarity of the code is more important.

def quickSort(items: List[Product]): List[Product] = {
  items match {
    case Nil => Nil
    case pivot :: tail =>
      val smaller = tail.filter(_.price <= pivot.price)
      val larger = tail.filter(_.price > pivot.price)
      quickSort(smaller) ++ List(pivot) ++ quickSort(larger)
  }
}

Look at how much cleaner that is. No indices, no temporary variables, no mutation. We just split the world into "smaller than" and "larger than" and glue them back together.

The Stability of Merge Sort

One thing we haven't discussed is stability. A sort is stable if it preserves the relative order of elements with equal keys. If I have two products that both cost $10, but "Apple" came before "Banana" in the original list, a stable sort keeps "Apple" first.

Quick Sort isn't naturally stable. Merge Sort is. Let's implement it by breaking the list in half and then merging the sorted halves back together.

def mergeSort(items: List[Product]): List[Product] = {
  val n = items.length
  if (n <= 1) return items

  val middle = n / 2
  val left = items.take(middle)
  val right = items.drop(middle)

  def merge(l: List[Product], r: List[Product]): List[Product] = (l, r) match {
    case (Nil, _) => r
    case (_, Nil) => l
    case (lHead :: lTail, rHead :: rTail) =>
      if (lHead.price <= rHead.price) lHead :: merge(lTail, rHead :: rTail)
      else rHead :: merge(lHead :: lTail, rTail)
  }

  merge(mergeSort(left), mergeSort(right))
}

Notice the lHead.price <= rHead.price condition. That <= is the secret sauce. By preferring the element from the "left" side when prices are equal, we maintain the original order of the elements.

📋 Practical Task

Exercise: Building a Multi-Criteria Stable Sort for an Employee Directory

In this exercise, you will implement a custom sorting utility for an Employee directory. The goal is to sort employees primarily by their department (alphabetically) and secondarily by their yearsOfExperience (descending).

Requirements:

• Define a case class Employee(name: String, department: String, yearsOfExperience: Int).
• Implement a stable Merge Sort algorithm.
• Modify the comparison logic in your merge function so that:
  1. Employees in departments that come earlier in the alphabet are placed first.
  2. If two employees are in the same department, the one with more years of experience comes first.
• Test your implementation with a list of at least 5 employees where at least two belong to the same department but have different experience levels.