Scala 3 pure immutable recursive merge sort

ListMergeSort.scala

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 " ")

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 " ")