help with a merge sort

[scroce]

Hello everyone. I'm new to java. I'm trying to solve a merge sort problem and I'm stuck.

the following is what I've written so far, of a function that takes two presorted arrays of integers and is supposed to merge sort them into one:

public static int[] mergeSort(int[] array1, int[] array2)
    {
        int a1Len=array1.length;
        int a2Len=array2.length;
        int resultLen=array1.length+array2.length;
        int[] resultSet=new int[resultLen];
        int r=0;
        
        for(int i=0;i<a1Len;)                
        {
            for(int j=0;j<a2Len;)
            {             
             if(array1[i]<array2[j])
                {
                    resultSet[r]=array1[i];
                    r++;
                    i++;
                }
                else
                {   
                    resultSet[r]=array2[j];
                    r++;                    
                    j++;
                }             
            }           
        }       
        return resultSet;
    }

This works until either i or j meets its limit in the for loop.

In pseudo code, I know that I have to say something like:

"If either i or j is out of range then exit this portion of the loop and take all of the remaining integers in the other array (i.e. the array that hasn't been traversed) and put them into the result set"

but i'm having trouble telling it to do this, since something like if(array1=null) doesn't seem to be acceptable syntax.

can somebody give me a hint? - thanks.


I am a nobody, and nobody is perfect; therefore, I am perfect.

 

[sedj]

Yeah, your loops are a bit screwed up with how you are accessing the arrays, this code runs (but does nothing) ... I am a bit confused by what you are trying to achieve, anyway, maybe this will help ...

		int[] array1 = new int[] { 1,2,3};
		int[] array2 = new int[] { 4,5,6};
        int a1Len=array1.length;
        int a2Len=array2.length;
        int resultLen=array1.length+array2.length;
        int[] resultSet=new int[resultLen];
        int r=0;

        for(int i = 0; i < a1Len; i++) {
            for(int j = 0;j < a2Len; j++) {
				System.err.println("here " +array1[i] +" " +array2[j] +" " +r);
             	if(array1[i]<array2[j]) {
                    resultSet[r]=array1[i];
                    //r++; 
                    
             	} else {
                    resultSet[r]=array2[j];
                    //r++;
                    
             	}
            }
        }

 

[scroce]

OK - thanks for the reply I'll take a looksee at this.

just FYI -

I'm trying to do an exercise from a manual. It explains this thing they call a merge sort, and they explain it like, this and want you to write code that does it:

you have two separate decks of cards - deck i and deck j, each already pre-sorted. The decks might be different sizes. You want to sort them into a result set, deck r by flipping the first of each deck over, comparing them, and then putting the lower one into the result pile.

Next you turn the next card over on the pile and compare the two face up cards, and again put the lower one into the next slot on the result pile.

You continue this until one pile is finished and put any remaining cards in the result pile as they are.

My code tries to follow that reasoning, but gets tripped up when one of the deck runs out of cards - casting back a "out of bounds" exception.




I am a nobody, and nobody is perfect; therefore, I am perfect.

 

[scroce]

sedj - your post helped - thanks!

ok - after much monkeying, here is a workable result. I've probably reinvented the wheel here, but I guess that's what you do when you learn a new language.

For anyone else learning, I was able to decipher this by writing it first in a language that I'm a little more familiar with (VB) and then I "translated" it to java.

public static int[] mergeSort(int[] array1, int[] array2)
    {
        int a1Len=array1.length;
        int a2Len=array2.length;
        int resultLen=array1.length+array2.length;
        int[] resultSet=new int[resultLen];
        int r=0;
        int i=0;
        int j=0;
        int x=0;
        
        for(x=0;x<resultLen;x++)
        {
            if(i==a1Len)
            {
                if(j<=a2Len)
                {
                    resultSet[r]=array2[j];
                    j++;
                }
            }            
            else if(j==a2Len)
            {
                if(i<=a1Len)
                {
                    resultSet[r]=array1[i];
                    i++;
                }                
            }
            else
            {
                if(array1[i]<=array2[j])
                {
                    resultSet[r]=array1[i];
                    i++;
                }
                else
                {
                    resultSet[r]=array2[j];
                    j++;
                }
            }
            //This is a helpful debugging tool
            System.err.println(resultSet[r]);
            r++;              
        }
        return resultSet;
        
        
        
    }

I am a nobody, and nobody is perfect; therefore, I am perfect.