CODEWITHSUNDEEP
javastringsortingmerge
Hunter Moore
Hunter Moore

Reputation: 37

Incorrect Merge Sorting

I'm working on a merge sorting program that sorts movies alphabetically by title. However, it is not sorting the list to completion. I have studied merge sorting, and looked at various other examples both on this site and elsewhere, and cannot find my error. 

public static Movie4[] myMovies;

/**
 * printMovies traverses an array of movies and prints each respective title
 */
public static void printMovies(Movie4[] movies)
{
    for (int i = 0; i < movies.length; i ++)
    {
        System.out.println(movies[i]);
    }
}

/**
 * sortTitles sorts an array of movies alphabetically by title
 */
public static void sortTitles(Movie4[] movies, int low, int high)
{
    if (low == high)
    {
        return;
    }
    else
    {
        Movie4[] firstHalf = new Movie4[movies.length  / 2];
        Movie4[] secondHalf = new Movie4[movies.length - movies.length / 2];
        int midpoint = (low + high) / 2;
        for (int i = 0; i < firstHalf.length; i ++)
        {
            firstHalf[i] = movies[i];
        }
        for (int i = 0; i < secondHalf.length; i ++)
        {
            secondHalf[i] = movies[i + movies.length / 2];
        }
        sortTitles(firstHalf, low, midpoint);
        sortTitles(secondHalf, midpoint + 1, high);
        mergeTitles(movies, firstHalf, secondHalf);
    }
}

/**
 * mergeTitles works in conjunction with sortTitles to merge sort an array of Movie4 objects 
 */
public static void mergeTitles(Movie4[] movies, Movie4[] first, Movie4[] second)
{
    int i = 0;
    int i2 = 0;
    for (int index = 0; index < movies.length; index ++)
    {
        if (i2 >= second.length || (i < first.length && 
                                        first[i].getTitle().compareTo(second[i2].getTitle()) < 0))
        {
            movies[index] = first[i];
            i ++;
        }
        else
        {
            movies[index] = second[i2];
            i2 ++;
        }
    }
}

public static void main(String[] args)
{
    myMovies = new Movie4[10];
        myMovies[0] = new Movie4("The Muppets Take Manhattan", 2001, "Columbia Tristar");
        myMovies[1] = new Movie4("Mulan Special Edition", 2004, "Disney");
        myMovies[2] = new Movie4("Shrek 2", 2004, "Dreamworks");
        myMovies[3] = new Movie4("The Incredibles", 2004, "Pixar");
        myMovies[4] = new Movie4("Nanny McPhee", 2006, "Universal");
        myMovies[5] = new Movie4("The Curse of the Were-Rabbit", 2006, "Aardman");
        myMovies[6] = new Movie4("Ice Age", 2002, "20th Century Fox");
        myMovies[7] = new Movie4("Lilo and Stich", 2002, "Disney");
        myMovies[8] = new Movie4("Robots", 2005, "20th Century Fox");
        myMovies[9] = new Movie4("Monsters Inc.", 2001, "Pixar");

    System.out.println("Original List:");
    System.out.println();
    printMovies(myMovies);
    System.out.println();
    System.out.println("List Sorted by title, ascending:");
    System.out.println();
    sortTitles(myMovies, 0, myMovies.length - 1);
    printMovies(myMovies);
}

Please assume that the getTitle() method is defined elsewhere and simply returns the first String of each object, the title. Here is the incorrect output;

List Sorted by title, ascending:

Ice Age, 2002, 20th Century Fox.
Lilo and Stich, 2002, Disney.
Mulan Special Edition, 2004, Disney.
Robots, 2005, 20th Century Fox.
Monsters Inc., 2001, Pixar.
Shrek 2, 2004, Dreamworks.
The Curse of the Were-Rabbit, 2006, Aardman.
The Incredibles, 2004, Pixar.
Nanny McPhee, 2006, Universal.
The Muppets Take Manhattan, 2001, Columbia Tristar.

I believe the error may be with my conditional statement, because if I set the compareTo value to > 0, it sorts correctly, just in the wrong order.

Upvotes: 0

Views: 33

Answers (1)

Ted Hopp
Ted Hopp

Reputation: 234807

You shouldn't be allocating new arrays or copying elements. Everything inside sortTitles() should be managed using low and high. Likewise, you should not be passing three arrays to mergeTitles(); instead, pass a single array and the values low, midpoint and high to let it know what parts of the array to merge.

Your current code seems to have a fencepost problem: you compute midpoint using (low + high) / 2, but use movies.length / 2 for the length of the first array. Since low starts off as 0 and high starts off as myMovies.length - 1, these lengths will differ when myMovies.length is even. You may have other indexing problems, but I didn't look too deeply into that because the entire approach is flawed, as I described in the first paragraph.

Upvotes: 3

Related Questions