# MergeSort wierdness

4 messages
Open this post in threaded view
|
Report Content as Inappropriate

## MergeSort wierdness

 Hello,       When I implemented the following for the MergeSort I got the StackOverflowError.Consider the highlighted code.  `object MergeSort {  def mergeSort(xs: List[Int]): List[Int] = {    val n = xs.length    if ((n / 2) == 0) xs    else {      val (xsh, ysh) = xs splitAt n      merge(mergeSort(xsh), mergeSort(ysh))    }  }  def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match {    case (Nil, ys) => ys    case (xs, Nil) => xs    case (xs, ys)  => if (xs.head < ys.head) xs.head :: merge(xs.tail, ys) else ys.head :: merge(xs, ys.tail)  }  def main(args: Array[String]) = {    println(mergeSort(List(9, 8, 4, 6, 3, 2, 9, 1, 5, 7)))  }}`If I change the highlighted code as given below (green highlighted) it is working.In the previous case all I did was doing the calculation and expression in one statement which is inside the if conditionIn the following working case I did the calculation and assign it to a value type and check that value type inside the if statement.To me it looks like both are correct. Can anyone help me why the above code is not working and the code below is working.`object MergeSort {  def mergeSort(xs: List[Int]): List[Int] = {    val n = xs.length / 2    if (n == 0) xs    else {      val (xsh, ysh) = xs splitAt n      merge(mergeSort(xsh), mergeSort(ysh))    }  }  def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match {    case (Nil, ys) => ys    case (xs, Nil) => xs    case (xs, ys)  => if (xs.head < ys.head) xs.head :: merge(xs.tail, ys) else ys.head :: merge(xs, ys.tail)  }  def main(args: Array[String]) = {    println(mergeSort(List(9, 8, 4, 6, 3, 2, 9, 1, 5, 7)))  }}` -- You received this message because you are subscribed to the Google Groups "scala-user" group. To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email]. For more options, visit https://groups.google.com/d/optout.
Open this post in threaded view
|
Report Content as Inappropriate

## Re: MergeSort wierdness

 You refer to n later in the code ("xs splitAt n"), so it matters whether n equals the length or half the length, which is different in the two versions. -- You received this message because you are subscribed to the Google Groups "scala-user" group. To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email]. For more options, visit https://groups.google.com/d/optout.
Open this post in threaded view
|
Report Content as Inappropriate

## Re: MergeSort wierdness

 Thanks Seth. makes sense. I overlooked it. Sorry about that.On Friday, March 17, 2017 at 10:38:26 AM UTC-5, Seth Tisue wrote:You refer to n later in the code ("xs splitAt n"), so it matters whether n equals the length or half the length, which is different in the two versions. -- You received this message because you are subscribed to the Google Groups "scala-user" group. To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email]. For more options, visit https://groups.google.com/d/optout.