Quantcast

MergeSort wierdness

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

MergeSort wierdness

Mohamed R Alla Pitchai
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 condition

In 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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: MergeSort wierdness

Seth Tisue-3
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: MergeSort wierdness

Mohamed R Alla Pitchai


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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: MergeSort wierdness

Seth Tisue-3
On Fri, Mar 17, 2017 at 1:43 PM, Mohamed R Alla Pitchai <[hidden email]> wrote:


Thanks Seth. makes sense. I overlooked it. Sorry about that.

no worries. easy to miss!

--
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.
Loading...