Tail recursive MergeSort for Tuples in Scala - Stack Overflow

admin2025-04-06  0

so im trying to make a mergesort for list with tuples, but no matter what i look at i dont see anything wrong with the implementation im doing. But still @tailrec is not being detected by Scala for some reason. When i do an implementation for a List[Int] it recognized it but not for tuple, eventhough the implementation im doing is basically the same. Would appreaciate a new set of eyes on this cause i dont really see where the issue is (yes tailrec is imported and merge cant just be "def merge" cause ill get this error saying how it needs to be either private or final)

Just how i have it right now tailrec is white instead of green

TailRec optimisation not applicable, method merge is neither private nor final so can be overridden
  def mergeSort(lst: List[(Int, Int)]): List[(Int, Int)] = {
    if (lst.length <= 1) lst
    else {
      val mid = lst.length / 2
      val left = mergeSort(lst.take(mid))
      val right = mergeSort(lst.drop(mid))
      merge(left, right)
    }
  }

  @tailrec
  final def merge(left: List[(Int, Int)], right: List[(Int, Int)], acc: List[(Int, Int)] = Nil): List[(Int, Int)] = (left, right) match {
    case (Nil, _) => acc.reverse ::: right // Agregar lo que queda y revertir el acumulador
    case (_, Nil) => acc.reverse ::: left
    case (h1 :: t1, h2 :: t2) =>
      if (h1._1 <= h2._1) merge(t1, right, h1 :: acc)
      else merge(left, t2, h2 :: acc)
  }
转载请注明原文地址:http://conceptsofalgorithm.com/Algorithm/1743871433a222136.html

最新回复(0)