Java: Mergesort for ArrayList does not work

Question

It does the comparison of Objects properly but doubles the size of list with duplicate objects.

public static void mergeSort(List<Person> list) {
        List<Person> helper = new ArrayList<Person>(list.size());
        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) {
        for(int i=low; i<= high; 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.add(current, helper.get(helperLeft));
                helperLeft++;
            } else {
                list.add(current, helper.get(helperRight));
                helperRight++;
            }
            current++;
        }

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

    }

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;
    }
}

Test Objects

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"));

You should consider giving feedback to your other questions answer before asking new one stackoverflow.com/questions/28844109/… — Jean-François Savard
– Jean-François Savard, Commented Mar 4, 2015 at 2:49

MadProgrammer · Accepted Answer · 2015-03-04 03:16:50Z

3

There are several issues...

Don't use List#add, use List#set

Instead of...

    while(helperLeft <= middle && helperRight <= high) {
        if(helper.get(helperLeft).isLessThan( helper.get(helperRight))) {
            list.add(current, helper.get(helperLeft));
            helperLeft++;
        } else {
            list.add(current, helper.get(helperRight));
            helperRight++;
        }
        current++;
    }

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

use...

    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));
    }

Lists, like arrays, are zero indexed, so instead of...

    for (int i = low; i <= high; i++) {
        helper.add(i, list.get(i));
    }

you should be using

    for (int i = low; i < high; i++) {
        helper.add(i, list.get(i));
    }

And instead of...

    while (helperLeft <= middle && helperRight <= high) {

you should be using...

    while (helperLeft < middle && helperRight < high) {

So, after making corrections to accomidate for the missing code in your example (getPersonDay for example), I get something like...

----Unsorted
1L; 10/01/1960
1L; 04/05/1978
1L; 09/17/1986
1L; 02/15/1971
1L; 07/01/1971

----Sorted
1L; 10/01/1960
1L; 02/15/1971
1L; 07/01/1971
1L; 04/05/1978
1L; 09/17/1986

edited Mar 4, 2015 at 3:16

answered Mar 4, 2015 at 2:55

MadProgrammer

348k22 gold badges243 silver badges379 bronze badges

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

3 Comments

Himanshu Yadav Over a year ago

Interesting part was not using set in the for loop.

Himanshu Yadav Over a year ago

I think add was correct. set was throwing IndexOutOfBoundException for me.

Himanshu Yadav Over a year ago

for (int i = low; i <= high; i++) { does not work with even number of items in the list.

luchy0120 · Accepted Answer · 2015-03-04 03:03:06Z

0

When high-low<2,you forget to sort this small scope of the List.You need to deal with that small case,as below

 private static void mergeSort(List<Person> list, List<Person> helper, int low, int high) {
    if(high - low<2) {
        sortTheSmallList(list,low,high);
    }else{
        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);
    }
}

answered Mar 4, 2015 at 3:03

luchy0120

551 silver badge6 bronze badges

Collectives™ on Stack Overflow

Java: Mergesort for ArrayList does not work

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related