This merge sort program is not giving the correct answer

Question

object MergeSort
{
    def merge(a:Array[Int],p:Int,q:Int,r:Int)
    {
        var i:Int=0
        var j:Int=0
        var k:Int=0

        var n1 = q-p+1
        var n2 = r-q

        var L : Array[Int] = new Array[Int](n1);
        var R : Array[Int] = new Array[Int](n2);

        for(i <-0 to n1-1)
        {
            L(i)=a(p+i);
        }

        for(j <-0 to n2-1)
        {
            L(j)=a(q+j);
        }


        i=0
        j=0
        k=0

        while (i < n1 && j < n2) {
            if (L(i) <= R(j)) {
                a(k) = L(i);
                i=i+1;
                k=k+1;
            } else {
                a(k) = R(j);
                k=k+1;
                j=j+1;
            }
        }
        while (i < n1) {
            a(k) = L(i);
            k=k+1;
            i=i+1;
        }
        while (j < n2) {
            a(k) = R(j);
            k=k+1;
            j=j+1;



        }
    }

    def mergeSort(a:Array[Int], p:Int,r:Int ):Unit =
    {
        if(p<r)
        {
        var q:Int = (p+r)/2
        mergeSort(a,p,q)
        mergeSort(a,q+1,r)
        merge(a,p,q,r)
        }
    }


    def main(args : Array[String])
    {
    var a = Array(5,7,3,9,8,2,1,6,4,0)
    println("array is")
    for ( x <- a ) 
        {
        println( x )
        }
    mergeSort(a,0,9)
    println("array after sorting is")
    for ( x <- a ) 
        {
        println( x )
        }
    }

}

output: array is 5 7 3 9 8 2 1 6 4 0

array after sorting is
0 0 0 0 0 6 2 1 6 4

This program is giving incorrect answer. perhaps due to the low quality logic. I can't find the problem. I am Stuck for two days. Since it is a recursive program it's tough to trace it.I am a beginner. Any help would be appreciated.

Answer 1

You have to be very careful with indices. I have corrected a few mistakes take a look:

object Foo {

   def merge(a:Array[Int],p:Int,q:Int,r:Int)
    {
        //var i:Int=0
        //var j:Int=0
        //var k:Int=0 this is not C

        var n1 = q-p+1
        var n2 = r-q

        var L : Array[Int] = new Array[Int](n1);
        var R : Array[Int] = new Array[Int](n2);

        for(i <-0 until n1) // notice until
        {
            L(i)=a(p+i);
        }

        for(j <-0 until n2)
        {
            // copy to R not to L !!!
            R(j)=a(q+ 1 + j); // a(q) belongs to L !!!
        }


        var i=0
        var j=0
        var k=p // copy from p, not begining!

        while (i < n1 && j < n2) {
            if (L(i) <= R(j)) {
                a(k) = L(i);
                i=i+1;
                k=k+1;
            } else {
                a(k) = R(j);
                k=k+1;
                j=j+1;
            }
        }
        while (i < n1) {
            a(k) = L(i);
            k=k+1;
            i=i+1;
        }
        while (j < n2) {
            a(k) = R(j);
            k=k+1;
            j=j+1;



        }
    }


  def mergeSort(a: Array[Int], p: Int, r: Int): Unit =
    {
      if (p < r ) {
        var q: Int = (p + r) / 2
        mergeSort(a, p, q) // from p to q inclusive sorted
        mergeSort(a, q + 1, r) // from q + 1 to r inclusive sorted
        merge(a, p, q, r)
      }
    }

  def main(args: Array[String]) {
    var a = Array(5, 7, 3, 9, 8, 2, 1, 6, 4, 0)
    println(s"array is: ${a.toList}")

    mergeSort(a, 0, 9)
    println(s"array is: ${a.toList}")

  }

}