Merge Sort
Implementierung
package net.bitelligence.training.exercise.sorting.merge_sort;
public class MergeSort {
public int[] sort(int[] numbers) {
// ...
return numbers;
}
}package net.bitelligence.training.exercise.sorting.merge_sort;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
class MergeSortTest {
@Test
public void should_correctly_sort_mixed_arrays() {
final int[] unsorted1 = {};
final int[] unsorted2 = { 1 };
final int[] unsorted3 = { 2, 1 };
final int[] unsorted4 = { 2, 1, 3 };
final int[] unsorted5 = { 2, 4, 1, 3 };
final int[] unsorted6 = { 2, 1, 2, 3, 9 };
final int[] unsorted7 = { 1, 2, 3, 4, 5, 6 };
final int[] expected1 = {};
final int[] expected2 = { 1 };
final int[] expected3 = { 1, 2 };
final int[] expected4 = { 1, 2, 3 };
final int[] expected5 = { 1, 2, 3, 4 };
final int[] expected6 = { 1, 2, 2, 3, 9 };
final int[] expected7 = { 1, 2, 3, 4, 5, 6 };
assertArrayEquals(expected1, new MergeSort().sort(unsorted1));
assertArrayEquals(expected2, new MergeSort().sort(unsorted2));
assertArrayEquals(expected3, new MergeSort().sort(unsorted3));
assertArrayEquals(expected4, new MergeSort().sort(unsorted4));
assertArrayEquals(expected5, new MergeSort().sort(unsorted5));
assertArrayEquals(expected6, new MergeSort().sort(unsorted6));
assertArrayEquals(expected7, new MergeSort().sort(unsorted7));
}
}package net.bitelligence.training.exercise.sorting.merge_sort;
public class MergeSort {
/**
* Splitting the array in two recursively and recombine them recursively
* [1,3,2] ==> [1,3] [2] ==> [1,2,3]
*
* @param numbers Array with numbers to be sorted
* @return The passed array with all numbers in the correct order
*/
public int[] sort(int[] numbers) {
if (numbers.length <= 1) // no sorting needed when array only contains one or no elements
return numbers;
// create two new arrays half the size of the original array
final int leftSize = numbers.length / 2;
final int rightSize = numbers.length - leftSize;
final int[] left = new int[leftSize];
final int[] right = new int[rightSize];
// populate the newly created arrays with the elements from the original array
for (int i = 0; i < numbers.length; i++) {
if (i < leftSize)
left[i] = numbers[i];
else
right[i - leftSize] = numbers[i];
}
return mergeArrays(sort(left), sort(right));
}
/**
* Combines two sorted arrays to a single sorted array
* [1,3] [2] ==> [1,2,3]
*
* @param left Left sorted array
* @param right Right sorted array
* @return The merged sorted array from left and right
*/
private int[] mergeArrays(int[] left, int[] right) {
final int[] merged = new int[left.length + right.length];
int indexLeft = 0; // points to the index of the left array for the next comparison
int indexRight = 0; // points to the index of the right array for the next comparison
for (int i = 0; i < merged.length; i++) {
if (indexLeft >= left.length) // if the end of the left array is reached add right element
merged[i] = right[indexRight++];
else if (indexRight >= right.length) // if the end of the right array is reached add left element
merged[i] = left[indexLeft++];
else // adds the lowest element of the current left right comparison
merged[i] = left[indexLeft] < right[indexRight] ? left[indexLeft++] : right[indexRight++];
}
return merged;
}
}Funktionsweise
Mergesort betrachtet die zu sortierenden Daten als Liste und zerlegt sie in kleinere Listen, die jede für sich sortiert werden. Die kleinen sortierten Listen werden dann im Reißverschlussverfahren zu größeren sortierten Listen zusammengefügt (engl. to merge), bis eine sortierte Gesamtliste erreicht ist.
Das Bild veranschaulicht die drei wesentlichen Schritte eines Teile-und-herrsche-Verfahrens, wie sie im Rahmen von Mergesort umgesetzt werden. Der Teile-Schritt ist ersichtlich trivial (die Daten werden einfach in zwei Hälften aufgeteilt). Die wesentliche Arbeit wird beim Verschmelzen (merge) geleistet – daher rührt auch der Name des Algorithmus.
Bei der Betrachtung des in der Grafik dargestellten Verfahrens sollte man sich allerdings bewusst machen, dass es sich hier nur um eine von mehreren Rekursionsebenen handelt. So könnte etwa die Sortierfunktion, welche die beiden Teile 1 und 2 sortieren soll, zu dem Ergebnis kommen, dass diese Teile immer noch zu groß für die Sortierung sind. Beide Teile würden dann wiederum aufgeteilt und der Sortierfunktion rekursiv übergeben, sodass eine weitere Rekursionsebene geöffnet wird, welche dieselben Schritte abarbeitet. Im Extremfall (der bei Mergesort sogar der Regelfall ist) wird das Aufteilen so weit fortgesetzt, bis die beiden Teile nur noch aus einzelnen Datenelementen bestehen und damit automatisch sortiert sind. [1]
Hilfestellung
Tipp #1
Verstehen Sie die Grundidee des Algorithmus: Der Merge Sort funktioniert, indem das Array in kleinere Teilarrays aufgeteilt wird, diese Teilarrays sortiert und dann wieder zusammengefügt werden.
Tipp #2
Implementieren Sie die Rekursion korrekt: Der Merge Sort verwendet Rekursion, um die Teilarrays zu sortieren. Stellen Sie sicher, dass die Rekursion korrekt implementiert ist und das Array tatsächlich in kleinere Teilarrays aufgeteilt wird.
Tipp #3
Implementieren Sie das Zusammenführen der Teilarrays korrekt: Nachdem die Teilarrays sortiert wurden, müssen diese wieder zusammengefügt werden. Stellen Sie sicher, dass die Elemente aus den Teilarrays in der richtigen Reihenfolge in das endgültige Array übertragen werden.