merge sort in scala

merge.scala

	def msort(xs: List[Int]): List[Int] = {
		val n = xs.length / 2
		if (n == 0) xs
		else {
			def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match {
				case (Nil, ys) => ys
				case (xs, Nil) => xs
				case (x :: xs1, y :: ys1) =>
					if (x < y) x :: merge(xs1, ys)
					else y :: merge(xs, ys1)
			}
			val (fst, snd) = xs splitAt n
			merge(msort(fst), msort(snd))
		}
	}                                         //> msort: (xs: List[Int])List[Int]

	val l = List(7, 2, 5, 1, 3, 1, 0, 9, -10) //> l  : List[Int] = List(7, 2, 5, 1, 3, 1, 0, 9, -10)
	
	msort(l)                                  //> res0: List[Int] = List(-10, 0, 1, 1, 2, 3, 5, 7, 9)

# in python using tail recursion
def merge(l, r, acc):
    if not l:
        return acc + r
    elif not r:
        return acc + l
    else:
        if l[0] < r[0]:
            return merge(l[1:], r, acc + [l[0]])
        else:
            return merge(l, r[1:], acc + [r[0]])

def msort(seq):
    mid = len(seq) / 2
    if mid == 0:
        return seq
    else:
        left = msort(seq[:mid])
        right = msort(seq[mid:])
        return merge(left, right, [])