Skip to content

Instantly share code, notes, and snippets.

@rbobillot
Last active September 25, 2023 02:46
Show Gist options
  • Save rbobillot/4215fdcbec537e559f54bb71efe93ab1 to your computer and use it in GitHub Desktop.
Save rbobillot/4215fdcbec537e559f54bb71efe93ab1 to your computer and use it in GitHub Desktop.
Scala 3 pure immutable recursive merge sort
object Main:
@scala.annotation.tailrec
def merge(xs: List[Int], ys: List[Int], res: List[Int] = Nil): List[Int] =
(xs, ys) match
case (x :: t, y :: s) if x < y => merge(t, ys, res ::: x :: Nil) // using List concatenation to append `x` to `res`
case (x :: t, y :: s) => merge(xs, s, res ::: y :: Nil)
case (Nil, _) => res ::: ys
case (_, Nil) => res ::: xs
def mergeSort(lst: List[Int]): List[Int] =
lst.splitAt(lst.length / 2) match
case (Nil, _) => lst
case (xs, ys) => merge(mergeSort(xs), mergeSort(ys))
def main(av: Array[String]): Unit =
val lst = (9999 to 1 by -1).toList
val sorted = mergeSort(lst)
println(sorted mkString " ")
@rbobillot
Copy link
Author

rbobillot commented Sep 25, 2023

As the List is not the best type to use for sorting,
and the deconstruction in pattern matching is slowing things,
I did a simple rewrite using the Array type.

object Main:

  @scala.annotation.tailrec
  def merge(xs: Array[Int], ys: Array[Int], res: Array[Int] = Array.empty): Array[Int] =
    (xs, ys) match
      case (xs, ys) if ys.isEmpty        => res ++ xs
      case (xs, ys) if xs.isEmpty        => res ++ ys
      case (xs, ys) if xs.head < ys.head => merge(xs.tail, ys, res :+ xs.head)
      case (xs, ys)                      => merge(xs, ys.tail, res :+ ys.head)

  def mergeSort(lst: Array[Int]): Array[Int] =
    lst.splitAt(lst.length / 2) match
      case (xs, ys) if xs.isEmpty => lst
      case (xs, ys)               => merge(mergeSort(xs), mergeSort(ys))

  def main(av: Array[String]): Unit =
    val lst = (9999 to 1 by -1).toArray
    val sorted = mergeSort(lst)
    println(sorted mkString " ")

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment