0

So the code that I have for a merge sorter has a small bug in which a few items from an array list will be duplicated and thrown into an odd location

Sorted List    Unsorted List
apricot        gray
aqua           maize
bittersweet    mahogany
blue           green
brick          red
cornflower     apricot
flesh          bittersweet
gray           flesh
green          cornflower
lemon          orchid
magenta        pink
maize          orange
mahogany       maroon
bittersweet    blue
melon          yellow
orange         melon
orange         magenta
maroon         violet
blue           silver
pearl          tan
periwinkle     periwinkle
purple         turquoise
purple         thistle
olive          white
purple         sienna
tan            lemon
turquoise      pearl
brick          aqua
olive          brick
purple         olive
purple         purple

Here is the code I have written and I appreciate any and all feedback:

ArrayList<String> a = new ArrayList<String>();

public MergeSorter(ArrayList<String> aList)
{
    a = aList;
}

public void sort()
{
    if (a.size() <= 1) return;
    ArrayList<String> first = new ArrayList<String>();
    ArrayList<String> second = new ArrayList<String>();
    for (int i = 0; i < a.size()/2; i++)
        first.add(a.get(i));
    for (int i = a.size()/2; i < a.size(); i++)
        second.add(a.get(i));
    MergeSorter firstSorter = new MergeSorter(first);
    MergeSorter secondSorter = new MergeSorter(second);
    firstSorter.sort();
    secondSorter.sort();
    merge(first, second);
}

private void merge(ArrayList<String> first, ArrayList<String> second)
{
    int iFirst = 0;
    int iSecond = 0;
    int j = 0;

    while(iFirst < first.size() && iSecond < second.size())
    {
        if(first.get(iFirst).compareTo(second.get(iSecond)) < 0)
        {
            a.set(j, first.get(iFirst));
            iFirst++;
        }
        else
        {
            a.set(j, second.get(iSecond));
            iSecond++;
        }
        j++;
    }
    //System.arraycopy(first, iFirst, a, j, first.size() - iFirst);
    for (int i = iFirst; i < first.size() - iFirst; i++)
    {
        a.set(j, first.get(i));
        j++;
    }

    //System.arraycopy(second, iSecond, a, j, second.size() - iSecond);
    for (int i = iSecond; i < second.size() - iSecond; i++)
    {
        a.set(j, second.get(i));
        j++;
    }

}

}
2
  • Look at your merge function. What happens after the while loop when the 'second' array still has elements left to be copied? Will the final for loop be able to get to the final element of the array?
    – Chris Dodd
    Apr 16, 2015 at 2:01
  • @ChrisDodd Yep just noticed that i had forgotten to increment it. however, the test set of data that I'm using doesn't go through the second loop as for second has copied all of its values. the issue particularly lies in that first for loop of the merge class (it seems at least).
    – user4168341
    Apr 16, 2015 at 2:35

1 Answer 1

0

You're not iterating far enough:

for (int i = iFirst; i < first.size() - iFirst; i++)
{
    a.set(j, first.get(i));
    j++;
}
for (int i = iSecond; i < second.size() - iSecond; i++)
{
    a.set(j, second.get(i));
    j++;
}

At this point one of the lists has been completely consumed and you just need to copy all the remaining elements of the other list into the result list. Which means iterating from "the beginning of the end" (iFirst) to the end of the list (first.size()).

For some reason you subtract iFirst, so not all values are copied. Instead, the unsorted values (the ones with which the sorter was initialized) remain at the end of the list, and some of them will be duplicates from the part of the result list that actually got sorted.

This should work:

for (int i = iFirst; i < first.size(); i++)
{
    a.set(j, first.get(i));
    j++;
}
for (int i = iSecond; i < second.size(); i++)
{
    a.set(j, second.get(i));
    j++;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.