Java: Mergesort for objects of ArrayList

Question

I get IndexOutOfBoundException while copying original list to helper list. It only happens if original list has even number of objects. Not able to figure it out. Here is the code:

public static void mergeSort(List<Person> list) {
        List<Person> helper = new ArrayList<Person>();
        mergeSort(list, helper, 0, list.size());
    }

    private static void mergeSort(List<Person> list, List<Person> helper, int low, int high) {
        if(low < high) {
            int middle = (low+high)/2;
            mergeSort(list, helper, low, middle); //sort left half
            mergeSort(list, helper, middle+1, high); //sort right half
            merge(list, helper, low, middle, high); // merge
        }
    }

    private static void merge(List<Person> list, List<Person> helper, int low, int middle, int high) {
        //This loop throws Exception
        for(int i=low; i< high + 1; i++) {
            helper.add(i, list.get(i));
        }

        int helperLeft = low;
        int helperRight = middle + 1;
        int current = low;

        /**
         * Iterate through helper array, copying back smaller element in the original list 
         */
        while(helperLeft < middle && helperRight < high) {
            if(helper.get(helperLeft).isLessThan( helper.get(helperRight))) {
                list.set(current, helper.get(helperLeft));
                helperLeft++;
            } else {
                list.set(current, helper.get(helperRight));
                helperRight++;
            }
            current++;
        }

        //Copy remaining elements
        int remaining = middle - helperLeft;
        for(int j=0; j <= remaining; j++) {
            list.set(current+j, helper.get(helperLeft+j));
        }

    }

TestData

List<Person> list = new ArrayList<Person>();
        list.add(new Person("1L", "10", "1", "1960"));
        list.add(new Person("1L", "4", "5", "1978"));
        list.add(new Person("1L", "9", "17", "1986"));
        list.add(new Person("1L", "2", "15", "1971"));
        list.add(new Person("1L", "7", "1", "1971"));
        list.add(new Person("1L", "7", "1", "1972"));

Person.java

public class Person implements Comparable<Person>{

    private String personId;
    private String month;
    private String day;
    private String year;
    private Date personDay;
    static SimpleDateFormat formatter = new SimpleDateFormat("MM/dd/yyyy");

    public Person(String id, String month, String day, String year) {
        this.personId = id;
        this.month = month;
        this.day = day;
        this.year = year;
    }

    @Override
    public int compareTo(Person person) {
        return this.getPersonDay().compareTo(person.getPersonDay());
    }

    public boolean isLessThan(Person person) {
        boolean isLess = false;
         if(this.getPersonDay().compareTo(person.getPersonDay()) < 0) {
             isLess = true;
         }
         return isLess;
    }
}

Eran · Accepted Answer · 2015-03-04 13:14:53Z

1

I see a problem in the fact the in the initial call to mergeSort you pass list.size() as high.

Your merge method iterates i from low to high, including high (for(int i=low; i< high + 1; i++)), which means i gets out of bounds, since list.size() is out of bounds.

The initial call should probably be :

mergeSort(list, helper, 0, list.size() - 1);

answered Mar 4, 2015 at 13:14

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Himanshu Yadav Over a year ago

You are absolutely right. Nice catch. Sometime I just need another pair of eyes.

Gytis · Accepted Answer · 2017-06-19 19:57:41Z

Well, this code is not working, and I tried to use it fast, but failed, so I debugged it, and now thats how I reworked it to actually sort it properly:

private Person[] list;
private Person[] helper;

@Override
public void sort(List<Person> personList) {
    list = personList.toArray(new Person[personList.size()]);
    helper = new Person[list.length];
    mergeSort(0, list.length - 1);
    personList = Arrays.asList(list);
}

private void mergeSort(int low, int high) {
    if(low < high) {
        int middle = low + (high - low) / 2;
        mergeSort(low, middle); //sort left half
        mergeSort(middle + 1, high); //sort right half
        merge(low, middle, high); // merge
    }
}

private void merge(int low, int middle, int high) {
    //This loop throws Exception
    for(int i=low; i<= high; i++) {
        helper[i] = list[i];
    }

    int helperLeft = low;
    int helperRight = middle + 1;
    int current = low;

    /**
     * Iterate through helper array, copying back smaller element in the original list
     */
    while(helperLeft <= middle && helperRight <= high) {
        if(helper[helperLeft].compareTo(helper[helperRight]) < 1) {
            list[current] = helper[helperLeft];
            helperLeft++;
        } else {
            list[current] = helper[helperRight];
            helperRight++;
        }
        current++;
    }

    while (helperLeft <= middle) {
        list[current] = helper[helperLeft];
        current++;
        helperLeft++;
    }

}

I replaced List with Array, but you can always try to make it work with lists.

Collectives™ on Stack Overflow

Java: Mergesort for objects of ArrayList

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related