Merge Sort

Algorithm

Space: $O(n)$

Complexity: $O(nlogn)$

                   [8, 1, 7, 6, 4, 2, 5, 3, 9]
            [8, 1, 7, 6]                  [4, 2, 5, 3, 9]
         [8, 1]      [7, 6]           [4, 2]     [5, 3, 9] 
      [8]   [1]    [7]   [6]        [4]   [2]    [5]    [3, 9]
                                                       [3]   [9]
       ----------------------merge -----------------------------                          
                                      
        [1, 8]       [6, 7]                            [3, 9]
                                      [2, 4]      [3, 5, 9]
          [1, 6, 7, 8]                      [2, 3, 4, 5, 9]
                     [1, 2, 4, 5, 6, 7, 8, 9]     

Implementation

def ms(arr: Vector[Int]): Vector[Int] = {

  @tailrec
  def merge(l: Vector[Int], r: Vector[Int], out: Vector[Int]): Vector[Int] =
    (l, r) match {
      case (IndexedSeq(), IndexedSeq()) => out
      case ((l1: Int) +: ls, IndexedSeq()) =>
        merge(ls.asInstanceOf[Vector[Int]], Vector.empty, out :+ l1)
      case (IndexedSeq(), (r1: Int) +: rs) =>
        merge(Vector.empty, rs.asInstanceOf[Vector[Int]], out :+ r1)
      case ((l1: Int) +: ls, (r1: Int) +: rs) =>
        if (l1 < r1) merge(ls.asInstanceOf[Vector[Int]], r, out :+ l1)
        else merge(l, rs.asInstanceOf[Vector[Int]], out :+ r1)
    }

  if (arr.length <= 1) arr
  else {
    val mid = arr.length / 2
    val l = ms(arr.slice(0, mid))
    val r = ms(arr.slice(mid, arr.length))
    merge(l, r, Vector.empty)
  }

}