Algorithmensammlung: Sortierverfahren: Mergesort

Mergesort

Mergesort ist ein schneller Sortieralgorithmus. Die Komplexität von Mergesort ist im schlechtesten Fall, in der Landau-Notation ausgedrückt, $O(n\log n)$ .

Für weitere Informationen siehe Mergesort.

Implementierung in diversen Programmiersprachen

C#

public class Mergesort
{

	public static void sort(ref int[] array)
	{

		if (array.Length > 1) {
			int mitte = Convert.ToInt32(array.Length / 2);

			int[] links = new int[mitte];
			for (int i = 0; i <= links.Length - 1; i++) {
				links[i] = array[i];
			}

			int[] rechts = new int[array.Length - mitte];
			for (int i = mitte; i <= array.Length - 1; i++) {
				rechts[i - mitte] = array[i];
			}

			sort(ref links);
			sort(ref rechts);

			array = merge(ref links, ref rechts);
		}
	}

	private static int[] merge(ref int[] links, ref int[] rechts)
	{
		int[] neueArray = new int[links.Length + rechts.Length];
		int indexLinks = 0;
		int indexRechts = 0;
		int indexErgebnis = 0;

		while (indexLinks < links.Length && indexRechts < rechts.Length) {
			if (links[indexLinks] < rechts[indexRechts]) {
				neueArray[indexErgebnis] = links[indexLinks];
				indexLinks += 1;
			} else {
				neueArray[indexErgebnis] = rechts[indexRechts];
				indexRechts += 1;
			}
			indexErgebnis += 1;
		}

		while (indexLinks < links.Length) {
			neueArray[indexErgebnis] = links[indexLinks];
			indexLinks += 1;
			indexErgebnis += 1;
		}

		while (indexRechts < rechts.Length) {
			neueArray[indexErgebnis] = rechts[indexRechts];
			indexRechts += 1;
			indexErgebnis += 1;
		}

		return neueArray;
	}
}

Haskell

Zusammengesetzt aus generischen wiederverwendbaren Teilen. Man beachte, dass das Ersetzen der Anwendung von binaryFold durch eine Anwendung von foldr eine Implementation von Insertionsort ergibt.

mergeSort :: Ord a => [a] -> [a]
mergeSort = binaryFold merge [] . map (:[])

binaryFold :: (a -> a -> a) -> a -> [a] -> a
binaryFold (*) e = h where
	h [] = e
	h [x] = x
	h xs = h (pairwise xs)
	pairwise [] = []
	pairwise [x] = [x]
	pairwise (x1:x2:xs) = (x1*x2) : pairwise xs
	
merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge xxs@(x:xs) yys@(y:ys) = case compare x y of
	LT -> x : merge xs yys
	GT -> y : merge xxs ys
	EQ -> x : y : merge xs ys

Java

public static int[] sort(int[] array)
	{

		if (array.length > 1) {
			int mitte = (int)(array.length / 2);

			int[] links = new int[mitte];
			for (int i = 0; i <= mitte - 1; i++) {
				links[i] = array[i];
			}

			int[] rechts = new int[array.length - mitte];
			for (int i = mitte; i <= array.length - 1; i++) {
				rechts[i - mitte] = array[i];
			}

			links = sort(links);
			rechts = sort(rechts);

			return merge(links, rechts);
		}
		else
		{
			return array;
		}
	}

private static int[] merge(int[] links, int[] rechts)
{
	int[] neueArray = new int[links.length + rechts.length];
	int indexLinks = 0;
	int indexRechts = 0;
	int indexErgebnis = 0;

	while (indexLinks < links.length && indexRechts < rechts.length) {
		if (links[indexLinks] < rechts[indexRechts]) {
			neueArray[indexErgebnis] = links[indexLinks];
			indexLinks += 1;
		} else {
			neueArray[indexErgebnis] = rechts[indexRechts];
			indexRechts += 1;
		}
		indexErgebnis += 1;
	}

	while (indexLinks < links.length) {
		neueArray[indexErgebnis] = links[indexLinks];
		indexLinks += 1;
		indexErgebnis += 1;
	}

	while (indexRechts < rechts.length) {
		neueArray[indexErgebnis] = rechts[indexRechts];
		indexRechts += 1;
		indexErgebnis += 1;
	}

	return neueArray;
}

OCaml

let rec split l l1 l2 = match l with
  | [] -> (l1, l2)
  | [h] -> split [] (h::l1) l2
  | h1::h2::t -> split t (h1::l1) (h2::l2);;

let rec merge l1 l2 = match (l1, l2) with
  | ([], []) -> []
  | (h::t, []) -> h::(merge t [])
  | ([], h::t) -> h::(merge [] t)
  | (h1::t1, h2::t2) -> if h1 < h2 then h1::(merge t1 l2) else h2::(merge l1 t2);;

let rec mergesort l = match l with
  | [] -> []
  | [h] -> [h]
  | _ -> let (l1, l2) = split l [] [] in merge (mergesort l1) (mergesort l2);;

Visual Basic .NET

Public Class Mergesort

    Public Shared Sub sort(ByRef array As Integer())
        If array.Length > 1 Then

            Dim mitte As Integer = CInt(array.Length / 2)

            Dim links(mitte - 1) As Integer
            For i As Integer = 0 To links.Length - 1
                links(i) = array(i)
            Next

            Dim rechts(array.Length - mitte - 1) As Integer
            For i As Integer = mitte To array.Length - 1
                rechts(i - mitte) = array(i)
            Next
            
            sort(links)
            sort(rechts)

            array = merge(links, rechts)
        End If
    End Sub

    Private Shared Function merge(ByRef links As Integer(), ByRef rechts As Integer()) As Integer()
        Dim neueArray(links.Length + rechts.Length - 1) As Integer
        Dim indexLinks As Integer = 0
        Dim indexRechts As Integer = 0
        Dim indexErgebnis As Integer = 0

        While indexLinks < links.Length AndAlso indexRechts < rechts.Length
            If links(indexLinks) < rechts(indexRechts) Then
                neueArray(indexErgebnis) = links(indexLinks)
                indexLinks += 1
            Else
                neueArray(indexErgebnis) = rechts(indexRechts)
                indexRechts += 1
            End If
            indexErgebnis += 1
        End While

        While indexLinks < links.Length
            neueArray(indexErgebnis) = links(indexLinks)
            indexLinks += 1
            indexErgebnis += 1
        End While

        While indexRechts < rechts.Length
            neueArray(indexErgebnis) = rechts(indexRechts)
            indexRechts += 1
            indexErgebnis += 1
        End While

        Return neueArray
    End Function
End Class