Merge Sort ist ein stabiler Sortieralgorithmus, der nach dem Prinzip “Sortieren durch Mischen” arbeitet.
Idee
- Die Liste wird per Divide and Conquer immer weiter halbiert
- Die Elemente werden in einem temporären Array sortiert und zurückgeschrieben
Implememtierung
void mergeSort(ArrayList<Integer> list, int start, int end) {
if(start < end) {
int size = end - start;
int median = start + (size / 2);
mergeSort(list, start, median);
mergeSort(list, median + 1, end);
merge(list, start, median, end);
}
}
void merge(ArrayList<Integer> list, int start, int median, int end) {
ArrayList<Integer> temp = new ArrayList<>();
int counterA = start;
int counterB = median + 1;
while(counterA <= median && counterB <= end) {
if(list.get(counterA) < list.get(counterB)) {
temp.add(list.get(counterA));
counterA++;
}
else {
temp.add(list.get(counterB));
counterB++;
}
}
while(counterA <= median) {
temp.add(list.get(counterA));
counterA++;
}
while(counterB <= end) {
temp.add(list.get(counterB));
counterB++;
}
for(int i = start; i <= end; i++) {
list.set(i, temp.get(i-start));
}
}