Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 8 of 8

Thread: MergeSort won't work

  1. #1
    Junior Member
    Join Date
    Oct 2010
    Posts
    27
    Thanks
    1
    Thanked 0 Times in 0 Posts

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


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,237
    Thanks
    176
    Thanked 817 Times in 760 Posts
    Blog Entries
    5

    Default Re: MergeSort won't work

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

  3. #3
    Junior Member
    Join Date
    Oct 2010
    Posts
    27
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: MergeSort won't work

    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.

  4. #4
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,237
    Thanks
    176
    Thanked 817 Times in 760 Posts
    Blog Entries
    5

    Default Re: MergeSort won't work

    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.

  5. #5
    Junior Member
    Join Date
    Oct 2010
    Posts
    27
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: MergeSort won't work

    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);

  6. #6
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,237
    Thanks
    176
    Thanked 817 Times in 760 Posts
    Blog Entries
    5

    Default Re: MergeSort won't work

    See Arrays. You are quite close (and yes, how you are initially calling the function is the problem), but you want to tell the function to sort the entire array, not just portions of it. Read the article I linked to, then think how mergesort works (see Mergesort) to determine the correct parameters to pass to the function.
    Last edited by copeg; February 7th, 2011 at 06:26 PM.

  7. #7
    Junior Member
    Join Date
    Oct 2010
    Posts
    27
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: MergeSort won't work

    Ah-ha! I called it this way and it appears to be sorting just fine...
    mergeSort_srt(randomArray2,0,randomArray2.length-1);

  8. #8
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,237
    Thanks
    176
    Thanked 817 Times in 760 Posts
    Blog Entries
    5

    Default Re: MergeSort won't work

    Quote Originally Posted by joshft91 View Post
    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.

Similar Threads

  1. home work ..
    By shane1987 in forum Collections and Generics
    Replies: 8
    Last Post: November 16th, 2010, 08:45 AM
  2. My lines won't work!!!
    By The Mewzytion in forum What's Wrong With My Code?
    Replies: 5
    Last Post: July 2nd, 2010, 10:24 AM
  3. MergeSort not working Helppp please :(
    By colombianita2089 in forum What's Wrong With My Code?
    Replies: 4
    Last Post: May 17th, 2010, 08:56 PM
  4. Quick Question about Mergesort
    By Shadow703793 in forum Algorithms & Recursion
    Replies: 4
    Last Post: March 4th, 2010, 04:48 PM
  5. MergeSort
    By mgutierrez19 in forum Algorithms & Recursion
    Replies: 3
    Last Post: March 3rd, 2010, 07:46 PM