I am learning Scala and as a starting point I am trying to write a mergeSort algorithm. I am having problem with the performance of the merge part of it. 

I know that there are other implementations on this site but I would like to know why my one is not working well.

This is my code:

```
@tailrec
    def merge(l1:List[Int], l2:List[Int], acc:List[Int]): List[Int] = {

      if(l1.isEmpty || l2.isEmpty) l1 ++ l2 ++ acc
      else if(l1.last> l2.last) merge(l1.init, l2, l1.last :: acc)
      else  merge(l1, l2.init, l2.last :: acc)
    }

    val a1 = List(1,4,65,52151) 
    val a2 = List(2,52,124,5251,124125125)

    println(merge(a1, a2, List()))

```

How can you see the merge function is tail recursive and (if I am not wrong) the list methods that I am using should take constant time. 

The code gets very slow with a list of 100000 elements.