Merge Sort Java

Question

I am trying to make a merge sort method, but it keeps on giving the wrong sorts. Where do I have change to make it actually sort the array? What part of the code has to be different? Thank you for your time.

  public static void mergeSort(int[] array, int left,  int lHigh, int right, int rHigh) {  
        int elements = (rHigh - lHigh +1) ;  
        int[] temp = new int[elements];
        int num = left;
      while ((left <= lHigh) && (right <= rHigh)){
       if (a[left] <= array[right]) {
          temp[num] = array[left];
          left++;
        }
        else {
          temp[num] = array[right];
          right++;
        }
       num++;   
      }
     while (left <= right){
        temp[num] = array[left]; // I'm getting an exception here, and is it because of the num???
        left += 1;
        num += 1;  
     }  
     while (right <= rHigh) {
        temp[num] = array[right];
        right += 1;
        num += 1;  
     }  
     for (int i=0; i < elements; i++){
       array[rHigh] = temp[rHigh];
       rHigh -= 1;   
     }

EDIT: now the mergeSort doesn't really sort the numbers, can someone tell me where it specifically is? especially when I print the "Testing merge sort" part.

Answer 1

First of all, I'm assuming this is academic rather than practical, since you're not using a built in sort function. That being said, here's some help to get you moving in the right direction:

Usually, one can think of a merge sort as two different methods: a merge() function that merges two sorted lists into one sorted list, and mergeSort() which recursively breaks the list into single element lists. Since a single element list is sorted already, you then merge all the lists together into one big sorted list.

Here's some off-hand pseudo-code:

merge(A, B):
  C = empty list

  While A and B are not empty:
    If the first element of A is smaller than the first element of B:
      Remove first element of A.
      Add it to the end of C.
    Otherwise:
      Remove first element of B.
      Add it to the end of C.

  If A or B still contains elements, add them to the end of C.

mergeSort(A):
  if length of A is 1:
    return A

  Split A into two lists, L and R.

  Q = merge(mergeSort(L), mergeSort(R))

  return Q

Maybe that'll help clear up where you want to go.

If not, there's always MergeSort at wikipedia.

Additional:

To help you out, here are some comments inline in your code.

  public static void mergeSort(int[] array, int left,  int lHigh, int right, int rHigh) {   
        // what do lHigh and rHigh represent?

        int elements = (rHigh - lHigh +1) ;     
        int[] temp = new int[elements];
        int num = left;

      // what does this while loop do **conceptually**? 
      while ((left <= lHigh) && (right <= rHigh)){
       if (a[left] <= a[right]) {
          // where is 'pos' declared or defined?
          temp[pos] = a[left];
          // where is leftLow declared or defined? Did you mean 'left' instead?
          leftLow ++;
        }
        else {
          temp[num] = a[right];
          right ++;
        }
       num++;   
      }

     // what does this while loop do **conceptually**?
     while (left <= right){
        // At this point, what is the value of 'num'?
        temp[num] = a[left];
        left += 1;
        num += 1;   
     }
     while (right <= rHigh) {
        temp[num] = a[right];
        right += 1;
        num += 1;       
     }
     // Maybe you meant a[i] = temp[i]?
     for (int i=0; i < elements; i++){
       // what happens if rHigh is less than elements at this point? Could
       // rHigh ever become negative? This would be a runtime error if it did
       a[rHigh] = temp[rHigh];
       rHigh -= 1;      
     }

I'm purposefully being vague so you think about the algorithm. Try inserting your own comments into the code. If you can write what is conceptually happening, then you may not need Stack Overflow :)

My thoughts here are that you are not implementing this correctly. This is because it looks like you're only touching the elements of the array only once (or close to only once). This means you have a worst case scenario of O(N) Sorting generally takes at least O(N * log N) and from what I know, the simpler versions of merge sort are actually O(N^2).

More:

In the most simplistic implementation of merge sort, I would expect to see some sort of recursion in the mergeSort() method. This is because merge sort is generally defined recursively. There are ways to do this iteratively using for and while loops, but I definitely don't recommend it as a learning tool until you get it recursively.

Honestly, I suggest taking either my pseudo-code or the pseudo-code you may find in a wikipedia article to implement this and start over with your code. If you do that and it doesn't work correctly still, post it here and we'll help you work out the kinks.

Cheers!

And finally:

  // Precondition: array[left..lHigh] is sorted and array[right...rHigh] is sorted.
  // Postcondition: array[left..rHigh] contains the same elements of the above parts, sorted.
  public static void mergeSort(int[] array, int left,  int lHigh, int right, int rHigh) {   
        // temp[] needs to be as large as the number of elements you're sorting (not half!)
        //int elements = (rHigh - lHigh +1) ;
        int elements = rHigh - left;

        int[] temp = new int[elements];

        // this is your index into the temp array
        int num = left;

        // now you need to create indices into your two lists
        int iL = left;
        int iR = right;

        // Pseudo code... when you code this, make use of iR, iL, and num!
        while( temp is not full ) {
           if( left side is all used up ) {
             copy rest of right side in.
             make sure that at the end of this temp is full so the
               while loop quits.
           }
           else if ( right side is all used up) {
             copy rest of left side in.
             make sure that at the end of this temp is full so the
               while loop quits.
           }
           else if (array[iL] < array[iR]) { ... }
           else if (array[iL] >= array[iR]) { ... }
        }
 }