Java merge sort code not working

Question

Our teacher gave us the pseudocode for Merge Sort as below

enter image description here

I want to implement it in Java. My code is below:

public class MergeSorter {
/**
 * @param anArray
*/
    public MergeSorter(int[] anArray,int low, int high)
    {
        a = anArray;
        p = low;
        r = high;
    }
    public void sort()
    {
        if(p < r)
        {
           q = (p + r)/2;
           MergeSorter pqSorter = new MergeSorter(a, p, q);
           MergeSorter qrSorter = new MergeSorter(a, q + 1, r);
           pqSorter.sort();
           qrSorter.sort();
           merge(p, q, r);
        }
   }
private void merge(int low, int mid, int high)
{
   p = low;
   q = mid;
   r = high;
   int i;
   int j;
   int n1 = (q - p) + 1;
   int n2 = (r - q);
   int[] L = new int[n1+1];
   for (i = 0; i < n1; i++)
   {
       L[i] = a[(p + i)];
   }
   int[] R = new int[n2+1];
   for (j = 0; j < n2; j++)
       {
       R[j] = a[q + j];
       }
       L[n1] = Integer.MAX_VALUE;
       R[n2] = Integer.MAX_VALUE;
       i = 0;
       j = 0;
       for (int k = p; k < r; k++)
       {
           count = count + 1;
           if(L[i] <= R[j])
           {
               a[k] = L[i];
               i = i + 1;
           }
          else
           {
               a[k] = R[j];
               j = j + 1;
          }
       } 
    }
    private int[] a;
    private int p; 
    private int r;
    private int q;
    public int count = 0;
}

But this code is not working.I want to know where is the problem. Sorry for the wrong direction picture. Updated: Here is my other code.It now dose something but not sorted right. This is my test code below

    public static void main(String[] args) throws FileNotFoundException, IOException
    {
      int[] a = {1,4,6,2,10,7};
      MergeSorter sorter = new MergeSorter(a,0,a.length);
      sorter.sort();
      System.out.println(Arrays.toString(a));
     }

It output [1,2,4,4,2,7] as a result.

Where are a, p, r defined? How do you get the sorted array back to the calling code? Can you post the callingcode? — assylias
– assylias, Commented Mar 17, 2012 at 23:06
If you want people to even read your question, reduce the size of that image. — Don Roby
– Don Roby, Commented Mar 17, 2012 at 23:08
I strongly suggest debugging your code step by step to find and fix this kind of errors. That will improve your programming kung fu greatly. — lmcanavals
– lmcanavals, Commented Mar 17, 2012 at 23:24
To debug, just take your input and run your program through on paper. It won't take long to find out and it is a good learning. Start with a small input. — SeattleOrBayArea
– SeattleOrBayArea, Commented Mar 18, 2012 at 0:04

Daniel Fischer · Accepted Answer · 2012-03-18 00:23:35Z

1

You have a couple of off-by-one errors.

MergeSorter sorter = new MergeSorter(a,0,a.length);

The last index of an array is a.length - 1.

for (j = 0; j < n2; j++)
{
    R[j] = a[q + j];
}

The second half to be merged runs from index q+1 to r.

for (int k = p; k < r; k++)

The last index to be filled is r, not r-1, so the condition should be k <= r.

Further, the setting of the instance variables

p = low;
q = mid;
r = high;

in merge() is fishy. It doesn't hurt here because they are set to the values they already have, but in principle it's wrong.

answered Mar 18, 2012 at 0:23

Daniel Fischer

184k19 gold badges319 silver badges436 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

SuShiS Over a year ago

Thanks for helping. I fixed all errors. the program is now working. Could you explain further what did u mean the setting of the instance variables is wrong in principle?

Daniel Fischer Over a year ago

Not that extreme. Setting instance variables can be totally adequate. I meant that setting instance variables that carry important state of the object to the values of parameters of a method is dubious - and always wrong if done without checking that the new values represent the state correctly.

Pete · Accepted Answer · 2012-03-18 00:10:29Z

1

You are missing the floor function inside the Sort function at q = (p + r)/2. You mentioned you had fixed this. The next problem is your call to MergeSorter sorter = new MergeSorter(a,0,a.length); from main. I believe that has to be a.length - 1. The pseudo-code you have works for arrays where the first element is at index 1. But in java arrays start at index 0. After you make that change you then have 2 minor problems you need to adjust for inside the merge function. Goodluck.

answered Mar 18, 2012 at 0:10

Pete

10.9k10 gold badges56 silver badges75 bronze badges

1 Comment

SuShiS Over a year ago

Thanks for helping. I fixed all errors. the program is now working.

viktor · Accepted Answer · 2012-03-18 00:09:48Z

0

Your code doesn't correspond 100% to the pseudo-code. Hint: indexes

Just because Java is OO, doesn't mean you have to use object on everything. In this case you are better without it.

public static void mergeSort(int[] array) {
    mergeSort(array, 0, array.length-1);
}

private static void mergeSort(int[] array, int p, int r) {
    ...
}

private static void merge(int[] array, int p, int q, int r) {
    ...
}

answered Mar 18, 2012 at 0:09

viktor

1,31711 silver badges18 bronze badges

Comments

SeattleOrBayArea · Accepted Answer · 2012-03-18 00:32:56Z

I wrote a merge sort in C sometime back and it works fine. Try comparing if something strikes.

Also, check your indices, as pseudocode uses array indices from 1..n and when you write code, languages like C, Java use 0 as first index.

#include <stdio.h>


int A[] = {11, 32 ,2, 7, 1, 15 };

void
merge_sort(int A[], int startIndex, int endIndex)
{
    int q = 0;
    //Terminating condition
    if (!(startIndex < endIndex)) {
       return; 
    }

    q = (startIndex + endIndex) / 2;
    merge_sort(A, startIndex, q);
    merge_sort(A, q+1, endIndex);
    printf("\n merge with start[%d], q[%d], end[%d]", startIndex,q, endIndex);
    merge(A, startIndex, q, endIndex);
}

merge(int A[], int startIndex, int q, int endIndex)
{
   int i = 0; int j = 0; int k=0;  
   int C[endIndex - startIndex + 1];
   int A1[q - startIndex + 1];
   int A2[endIndex - q];
   int lenA1 =q - startIndex + 1;
   int lenA2 = endIndex - q; 
   int iterator = 0;
   int lenA = endIndex - startIndex + 1;

   for(iterator = 0; iterator < lenA1; iterator++) {
      A1[iterator] = A[iterator + startIndex]; 
      printf("\n Iterator1[%d]", iterator + startIndex);
   }

    dump(A1, lenA1);
   for(iterator = 0; iterator < lenA2; iterator++) {
      A2[iterator] = A[iterator + q + 1]; 
      printf("\n Iterator2[%d]", iterator + q + 1);
   }

    dump(A2, lenA2);

   for (iterator = startIndex; iterator < (endIndex - startIndex + 1) && ((i < lenA1) && (j<lenA2)); iterator++)
   {
       if (A1[i] <= A2[j]) {
           A[k] = A1[i]; 
           printf("\n\t--A[k]--");
           k+=1;
           i+=1; 
       } else {
           A[k] = A2[j];
           printf("\n\t****A[k]***");
           j+=1; 
           k+=1;      
       }
   }
   if (j < lenA2) {
      for (iterator = j; iterator < lenA2; iterator++)
      {
           A[k] = A2[j];
           j+=1; 
           k+=1;      
      }
   } else if (i < lenA1) {
           A[k] = A1[i]; 
           k+=1;
           i+=1; 
   }
    dump(A, lenA);
    fflush(stdout);

}

void dump(int A[], int len)
{
    int i;
    printf("\n --------");
    for(i=0; i<len; i++)
    {
        printf("[%d] ", A[i]);
    }
}

int main()
{
    merge_sort(A, 0, 6);
    dump(A, 7);
//    dump(C, 7);
}

Collectives™ on Stack Overflow

Java merge sort code not working

4 Answers 4

2 Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related