Thread: Help with using mergesort to sort a list of names alphabetically?

Hi, I'm trying to sort a list of names alphabetically, case-insensitive by using the mergesort technique.
I wrote this code and when I trace it through on paper with an example array of names, it should work, but when I run it with an actual txt file, it's not correctly alphabetical.
I'd appreciate it if someone could take a look at my code and give me some ideas on what my problem might be.
Thanks in advance! (note: I also posted this question to java-forums.org and coderranch.org, as I've been working on this little problem for over five hours and am in desperate need of some help!)

public static void mergeSort(String[] names)  
    {  
        if (names.length >= 2)  
        {  
            String[] left = new String[names.length/2];  
            String[] right = new String[names.length-names.length/2];  
 
            for (int i = 0; i < left.length; i++)  
            {  
                left[i] = names[i];  
            }  
            for (int i = 0; i < right.length; i++)  
            {     
                right[i] = names[i + names.length/2];  
            }  
 
            mergeSort(left);  
            mergeSort(right);  
            merge(names, left, right);  
        }  
    }  
 
   // pre : result is empty; list1 is sorted; list2 is sorted  
   // post: result contains result of merging sorted lists;  
   // add merge method below  
 
    public static void merge(String[] names, String[] left, String[] right)  
    {  
        int i1 = 0;  
        int i2 = 0;  
 
        for (int i = 0; i < names.length; i++)  
        {  
            if (i2 >= right.length || (i1 < left.length && left[i1].compareToIgnoreCase(right[i1])<0))  
            {  
                names[i] = left[i1];  
                i1++;  
            } else  
            {  
                names[i] = right[i2];  
                i2++;                 
            }  
        }  
    }     
}

Originally Posted by Norm

Can you post the contents of the list before the sort and after the sort so we can see what the code does?

Hi, yes, I created a "test" file, since the original file was too large to look at carefully.

The list would make a array {M, B, J, A, Z, C} without sorting

After being merge sorted, the array should look like {A, B, C, J, M, Z}, but instead it looks like {A, C, Z, B, J, M}

I've gone through the code step by step countless times and I can't seem to figure out what's wrong.

Thanks for any help!

That's what's confusing me, I traced the whole thing with that test run on paper, and I get the output I'm shooting for.
But not when I compile and run it. Please help!!