Java: Mergesort для ArrayList не работает

Question

Выполняет сравнение объектов должным образом, но удваивает размер списка с повторяющимися объектами.

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

испытаний объектов

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

Answer 1

Есть несколько вопросов ...

Не используйте List#add, используйте List#set

Вместо того, чтобы ...

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

использование ...

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

List s, как массивы, равны нулю индексируются, поэтому вместо того, чтобы ...

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

Вы должны использовать

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

И вместо того, чтобы ...

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

вы должны использовать ...

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

Таким образом, после внесения исправлений в accomidate недостающего кода в вашем примере (например getPersonDay), Я получаю что-то вроде ...

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

Answer 2

Когда высокий низкий < 2, вы забыли отсортировать эту небольшую сферу, чтобы просмотреть список, нужно иметь дело с этим небольшим случае, как показано ниже

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