Merge Sort implementation - Ошибка повторяющихся значений

Question

Я пытаюсь реализовать Merge Sort в Java на основе различных обучающих программ, доступных в Интернете, но в моем приведенном списке есть повторяющиеся значения. После большой отладки, я все еще не могу узнать, что случилось в моей реализации. Ниже приведен код:

public ArrayList<Integer> mergeSort(ArrayList<Integer> whole) 
{ 
    ArrayList<Integer> left = new ArrayList<Integer>(); 
    ArrayList<Integer> right = new ArrayList<Integer>(); 
    int center; 
    if(whole.size() ==1) return whole; 

    else 
    { 
     center = whole.size()/2; 

     for(int i = 0; i < center; i++ ) 
     { 
      left.add(whole.get(i)); 
     } 
     for(int i = center ; i < whole.size(); i++ ) 
     { 
      right.add(whole.get(i)); 
     } 

     left = mergeSort(left); 
     right = mergeSort(right); 

     whole = merge(left, right, whole); 
    return whole; 
    } 


} 


private ArrayList<Integer> merge(ArrayList<Integer> left, ArrayList<Integer> right, ArrayList<Integer> whole) 
{ 
    // TODO Auto-generated method stub 

    int leftIn = 0; 
    int rightIn = 0; 
    int wholeIn = 0; 

    while(leftIn <left.size() && rightIn < right.size()) 
    { 
     if(left.get(leftIn).compareTo(right.get(rightIn)) < 0) 
     { 
      whole.set(wholeIn, left.get(leftIn)); 

      leftIn++; 
     } 
     else 
     { 
      whole.set(rightIn, right.get(rightIn)); 

      rightIn++; 
     } 
     wholeIn++; 
    } 

    ArrayList<Integer> rest; 
    int restIn; 
    if(leftIn >= left.size()) 
    { 
     rest = right; 
     restIn = rightIn; 
    } 
    else 
    { 
     rest = left; 
     restIn = leftIn; 
    } 

    for(int i = restIn ; i < rest.size(); i++) 
    {  
     whole.set(wholeIn, rest.get(i)); 
     wholeIn++; 
    } 
    return whole; 

} 

Входной список: 1 5 -2 98 -221 3 8 7

Выход: -221 3 7 8 5 3 8 98

Answer 1

Ваш метод merge является случайно используя неправильный индекс rightIn в случае else случая цикла while. Это может привести к перезаписываемым значениям, проявляющимся в отсутствующих значениях и дублирующихся значениях.

Использовать wholeIn как if кейс. Изменить

whole.set(rightIn, right.get(rightIn)); 

в

whole.set(wholeIn, right.get(rightIn));