Thread: MergeSort won't work

Hey guys ...

Alright, I have my sort implemented and everything compiles fine. Up in my main I have an array of 100 random integers... then I call the mergeSort method with

mergeSort_srt(randomArray2,1,2);

I then print the array and the array is not sorted.

public static void mergeSort_srt(int array[],int lo, int n){
    int low = lo;
    int high = n;
    if (low >= high) {
      return;
    }
 
    int middle = (low + high) / 2;
    mergeSort_srt(array, low, middle);
        mergeSort_srt(array, middle + 1, high);
    int end_low = middle;
    int start_high = middle + 1;
    while ((lo <= end_low) && (start_high <= high)) {
      if (array[low] < array[start_high]) {
        low++;
            } else {
        int Temp = array[start_high];
        for (int k = start_high- 1; k >= low; k--) {
          array[k+1] = array[k];
        }
                array[low] = Temp;
                low++;
                end_low++;
                start_high++;
            }
        }
    }

Any help would be greatly appreciated.

I recommend posting an SSCCE that truly demos the problem, as your code seems to sort for me.

Thanks for the reply.
We're supposed to create two arrays and sort array2 so we ahve the first one as an original.
I stripped the code down as far as I could and got this... it still doesn't sort for me - prints fine, just not sort.

public class test {
 
	public static void main(String[] args) {
 
		int[] randomArray = new int[100];
		int[] randomArray2 = new int[100];
 
		LoadArray(randomArray);
 
		for (int i = 0; i < randomArray.length; i++) {
			randomArray2[i] = randomArray[i];
		}
 
		System.out.println("Merge Sorted:");
		mergeSort_srt(randomArray2,1,2);
		PrintArray(randomArray2);
 
 
	}
 
	/*
	 * Loads the array with random numbers
	 */
	public static void LoadArray(int[] A) {
		int arrayLength = A.length;
		for (int i = 0; i < arrayLength; i++) {
 
			A[i] = (int) (Math.random() * 100 + 1);
		}
	}
 
	/*
	 * Prints the array called
	 */
	public static void PrintArray(int[] A) {
		for (int i = 0; i < A.length; i++) {
			System.out.print((A[i] + ","));
			if ((i + 1) % 10 == 0) {
				System.out.println("");
			}
		}
	}
 
	public static void mergeSort_srt(int array[],int lo, int n){
	    int low = lo;
	    int high = n;
	    if (low >= high) {
	      return;
	    }
 
	    int middle = (low + high) / 2;
	    mergeSort_srt(array, low, middle);
	        mergeSort_srt(array, middle + 1, high);
	    int end_low = middle;
	    int start_high = middle + 1;
	    while ((lo <= end_low) && (start_high <= high)) {
	      if (array[low] < array[start_high]) {
	        low++;
	            } else {
	        int Temp = array[start_high];
	        for (int k = start_high- 1; k >= low; k--) {
	          array[k+1] = array[k];
	        }
	                array[low] = Temp;
	                low++;
	                end_low++;
	                start_high++;
	            }
	        }
	    }
}

Thanks again.

Think about how you are calling the mergesort function and how this function actually works..it divides and conquers based upon indexes (in this case indexes given to the function as parameters)...when the method is called anything outside those indexes (in the array) will not be sorted by that method call.

Hm.... I'm not super familiar with arrays yet, and I've tried different ways of calling the method but with no success. My thought process was that the lo, indicated by randomArray[0] through randomArray.length. It compiles fine but when I try to run it I get an "outofbounds" exception.

mergeSort_srt(randomArray2,randomArray[0],randomArray2.length);

Ah-ha! I called it this way and it appears to be sorting just fine...

mergeSort_srt(randomArray2,0,randomArray2.length-1);

Originally Posted by joshft91

Ah-ha! I called it this way and it appears to be sorting just fine...

Glad you figured it out...hope you understand how that actually affected the mergesort.