Algorithmensammlung: Sortierverfahren: Mergesort
Mergesort
BearbeitenMergesort ist ein schneller Sortieralgorithmus. Die Komplexität von Mergesort ist im schlechtesten Fall, in der Landau-Notation ausgedrückt, .
Für weitere Informationen siehe Mergesort.
Implementierung in diversen Programmiersprachen
Bearbeitenpublic 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;
}
}
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
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;
}
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);;
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