Java: Mergesort для объектов ArrayList

Question

Я получаю IndexOutOfBoundException при копировании исходного списка в список помощников. Это происходит только в том случае, если в исходном списке имеется четное количество объектов. Не в состоянии понять это. Вот код:

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

Answer 1

Я вижу проблему в самом деле в первоначальном вызове к вам пройти слияние list.size() как high.

Ваш merge метод перебирает i от low до high, в том числе high (for(int i=low; i< high + 1; i++)), что означает i выходит за пределы, так как list.size() находится вне границ.

Первоначальный вызов, вероятно, следует:

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

Answer 2

Ну, этот код не работает, и я пытался использовать это быстро, но не удалось, поэтому я отлажена, а теперь вот как я переработал его фактически сортировать это правильно:

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

} 

я заменил список с Array, но вы всегда можете попытаться сделать его работу со списками.