Mergesort
General Information
Algorithmic problem: Sorting based on pairwise comparison
Type of algorithm: recursion
Abstract View
Invariant: After a recursive call, the input sequence of this recursive call is sorted.
Variant: For a recursive call on a subsequence
Break condition: The current subsequence of the recursive call is a singleton.
Induction Basis
Abstract view: Nothing to do on a singleton.
Implementation: Ditto.
Proof: A singleton is trivially sorted.
Induction Step
Abstract view: The sequence is divided into two subsequences of approximately half size, it does not matter at all in which way this is done. Both subsequences are sorted recursively using Mergesort. The sorted subsequences are "merged" into one using algorithm Merge.
Implementation: Obvious.
Correctness: By induction hypothesis, the recursive calls sort correctly. So, correctness of Merge implies correctness of Mergesort.
Complexity
Statement: The complexity is in
Proof: Obviously, the variant is correct. So, the lengths of
Example implementations
Java
public static <T> void mergesort(List<T> liste, Comparator<T> cmp) {
if (liste.size() <= 1)
return;
LinkedList<T> teilliste1 = new LinkedList<T>(); // leer
LinkedList<T> teilliste2 = new LinkedList<T>();
zerlegeInTeillisten(liste, teilliste1, teilliste2);
mergesort(teilliste1, cmp);
mergesort(teilliste2, cmp);
liste.clear();
merge(teilliste1, teilliste2, liste, cmp);
}
// -----------------
public static <T> void zerlegeInTeillisten(List<T> liste,
List<T> teilliste1, List<T> teilliste2) {
ListIterator<T> it = liste.listIterator();
for (int i = 0; i < liste.size(); i++) {
T elem = it.next();
if (i <= liste.size() / 2)
teilliste1.add(elem); // Haengt elem hinten an teilliste1 an
else
teilliste2.add(elem); // Dito teilliste2
}
}