Почему это не работает mergeSort?

Question

Итак, цель этого бита моей программы состоит в том, чтобы принять несортированный список объектов и отсортировать его в соответствии с методом getRaised() в каждом объекте, который возвращает целое число, используя рекурсивный метод mergeSort. Программа работает без ошибок, но не сортирует arraylist.

public static void mergeSort(ArrayList<Runner> runners, int min, int max){ 
    if(min < max){ 
     int mid = (min+max)/2; 
     mergeSort(runners, min, mid); 
     mergeSort(runners, mid+1, max); 
     merge(runners, min, mid, max); 
    } 
} 
public static void merge(ArrayList<Runner> runners, int first, int mid, int last){ 
    ArrayList<Runner> temp = new ArrayList<>(); 
    temp = runners; 
    int f1 = first; 
    int l1 = mid; 
    int f2 = mid+1; 
    int l2 = last; 
    int index = f1; 

    for(int i = 0; i < runners.size(); i++){ 
     temp.add(runners.get(i)); 
    } 

    while(f1 <= l1 && f2 <= l2){ 
     if(runners.get(f1).getRaised() < runners.get(f2).getRaised()){ 
      temp.set(index, runners.get(f1)); 
      f1++; 
     }else{ 
      temp.set(index, runners.get(f2)); 
      f2++; 
     } 
     index++; 
    } 
    while(f1 <= l1){ 
     temp.set(index, runners.get(f1)); 
     f1++; 
     index++; 
    } 
    while(f2<=l2){ 
     temp.set(index, runners.get(f1)); 
     f2++; 
     index++; 
    } 
    for(int i = 0; i<=runners.size();i++){ 
     runners.set(i,temp.get(index)); 
    } 

} 

Это весь класс:

import java.util.ArrayList; 

public class Donation { 
    protected static ArrayList<Runner> Runners = new ArrayList<Runner>(); 
    public Donation(ArrayList<Runner> runners){ 
    for(int i = 0; i < runners.size(); i++){ 
     Runners.add(runners.get(i)); 
    }  
    mergeSort(Runners, 0,Runners.size()-1); 
} 

public void addRunner(String n, String id, double r){ 
    Runners.add(new Runner(n, id, r)); 
} 
public String displayInfo(int index){ 
    String str = Runners.get(index).toString(); 
    return str; 
} 
public void addDonations(int index, double amt){ 
    Runners.get(index).Raised+=amt; 
} 
public double getSum(){ 
    double sum=0; 
    for(int i = 0; i < Runners.size(); i++){ 
     sum+=Runners.get(i).Raised; 
    } 
    return sum; 
} 
public ArrayList<Runner> getRunnerObj(){ 
    return Runners; 
} 
public String goldenSneaker(){ 
    String gold = ""; 

    return gold; 
} 
public String silverSneaker(){ 
    String silver = ""; 

    return silver; 
} 
public String bronzeSneaker(){ 
    String bronze = ""; 

    return bronze; 
} 
public String achillesHeel(){ 
    String ach = ""; 

    return ach; 
} 

public void writeToFile(){ 

} 

public static void mergeSort(ArrayList<Runner> runners, int min, int max){ 
    if(min < max){ 
     int mid = (min+max)/2; 
     mergeSort(runners, min, mid); 
     mergeSort(runners, mid+1, max); 
     merge2(runners, min, mid, max); 
    } 
} 

public static void merge2(ArrayList<Runner> runners, int first, int mid, int last){ 
    ArrayList<Runner> temp = new ArrayList<>(); 
    int f1 = first; 
    int l1 = mid; 
    int f2 = mid+1; 
    int l2 = last; 
    int index = 0; 

    for(int i = first; i <=last; i++){ 
     temp.add(runners.get(i)); 
    } 

    while(f1 <= l1 && f2 <= l2){ 
     if(runners.get(f1).getRaised() < runners.get(f2).getRaised()){ 
      temp.set(index, runners.get(f1)); 
      f1++; 
     }else{ 
      temp.set(index, runners.get(f2)); 
      f2++; 
     } 
     index++; 
    } 
    while(f1 <= l1){ 
     temp.set(index, runners.get(f1)); 
     f1++; 
     index++; 
    } 
    while(f2<=l2){ 
     temp.set(index, runners.get(f2)); 
     f2++; 
     index++; 
    } 

    index = 0; 
    for(int i = first; i<=last;i++){ 
     runners.set(i,temp.get(index)); 
     index++; 
    } 
    } 
} 

Answer 1

Ваш метод слияния имеет несколько ошибок:

public static void merge(ArrayList<Runner> runners, int first, int mid, int last){ 
    ArrayList<Runner> temp = new ArrayList<>(); 
    temp = runners; // remove that line, otherwise your original list will 
        // continue growing until you run out of memory 
    int f1 = first; 
    int l1 = mid; 
    int f2 = mid+1; 
    int l2 = last; 
    int index = f1; 

    for(int i = 0; i < runners.size(); i++){ 
     temp.add(runners.get(i)); 
    } 

    while(f1 <= l1 && f2 <= l2){ 
     if(runners.get(f1).getRaised() < runners.get(f2).getRaised()){ 
      temp.set(index, runners.get(f1)); 
      f1++; 
     }else{ 
      temp.set(index, runners.get(f2)); 
      f2++; 
     } 
     index++; 
    } 
    while(f1 <= l1){ 
     temp.set(index, runners.get(f1)); 
     f1++; 
     index++; 
    } 
    while(f2<=l2){ 
     temp.set(index, runners.get(f1)); // typo - should be get(f2) 
     f2++; 
     index++; 
    } 
    for(int i = 0; i<=runners.size();i++){ // should be i<runners.size() 
              // to avoid index out of bounds 
              // exception 
     runners.set(i,temp.get(index)); // should be i instead of index 
    } 

} 

Это будет работать, хотя это не очень эффективно, так как при каждом обращении к merge вы копируете весь список источников в список тем и обратно в исходный список, в то время как единственные индексы, которые должны быть скопированы, - это индексы от первого до последнего.

Вот более эффективное слияние:

public static void merge(ArrayList<Runner> runners, int first, int mid, int last){ 
    ArrayList<Runner> temp = new ArrayList<>(); 
    int f1 = first; 
    int l1 = mid; 
    int f2 = mid+1; 
    int l2 = last; 

    while(f1 <= l1 && f2 <= l2){ 
     if(runners.get(f1).getRaised() < runners.get(f2).getRaised()){ 
      temp.add(runners.get(f1)); 
      f1++; 
     }else{ 
      temp.add(runners.get(f2)); 
      f2++; 
     } 
    } 
    while(f1 <= l1){ 
     temp.add(runners.get(f1)); 
     f1++; 
    } 
    while(f2<=l2){ 
     temp.add(runners.get(f2)); 
     f2++; 
    } 

    // copy only the merged range back to runners 
    int index = 0; 
    for(int i = first; i<=last;i++){ 
     runners.set(i,temp.get(index)); 
     index++; 
    } 

} 

Я проверил это путем изменения ArrayList<Runner> к ArrayList<Integer>, и она работает.