Der Mergesort Algorithmus ist ein stabiler Algorithmus zum Sortieren von Array, der Algorithmus arbeitet nach dem Prinzip „Teile und Hersche“. Dieser Algorithmus wurde 1945 von John von Neumann (externer Link) vorgestellt. Im Prinzip arbeitet das Mergesort mit 3 Schritten
- Teilen: der Mergesort unterteilt die Listen(Array) in immer kleinere Listen bis nur noch 1 Eintrag vorhanden ist.
- Sortieren: Dann werden alle Teilstücke für sich sortiert
- Zusammenfügen: Am Ende werden alle Teilstücke im Reißverschlussverfahren wieder zusammengefügt, bis eine sortierte gesamtliste erstellt worden ist.
public void MergeSort(int[] arr, int left, int right)
{
if (left < right)
{
int mid = left + (right - left) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
private void Merge(int[] arr, int left, int mid, int right)
{
int[] leftArray = new int[mid - left + 1];
int[] rightArray = new int[right - mid];
Array.Copy(arr, left, leftArray, 0, mid - left + 1);
Array.Copy(arr, mid + 1, rightArray, 0, right - mid);
int i = 0;
int j = 0;
for (int k = left; k < right + 1; k++)
{
if (i == leftArray.Length)
{
arr[k] = rightArray[j];
j++;
}
else if (j == rightArray.Length)
{
arr[k] = leftArray[i];
i++;
}
else if (leftArray[i] <= rightArray[j])
{
arr[k] = leftArray[i];
i++;
}
else
{
arr[k] = rightArray[j];
j++;
}
}
}Der Mergesort ist gerade bei großen Listen sehr effizient, allerdings benötigt dieser Algorithmus zusätzlichen Speicher (anders als z.B. beim Bubblesort oder Quicksort), dafür optimal für große Listen.