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 [math]\displaystyle{ S' }[/math] of [math]\displaystyle{ S }[/math], let [math]\displaystyle{ S_1' }[/math] and [math]\displaystyle{ S_2' }[/math] denote the subsequences of [math]\displaystyle{ S' }[/math] with which Mergesort is called recursively from that call. Then it is [math]\displaystyle{ |S_1'| \leq \lceil|S'| /2\rceil }[/math] and [math]\displaystyle{ |S_2'| \leq \lceil|S'| /2\rceil }[/math].
Break condition: The current subsequence of the recursive call is a singleton.
Remark: For a particular recursive call [math]\displaystyle{ C }[/math], we may, for example, choose the height of the recursion subtree with root [math]\displaystyle{ C }[/math] as the induction parameter. For conciseness, the induction parameter is omitted in the following.
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 [math]\displaystyle{ O(T\cdot n \log n) }[/math] in the best and worst case, where [math]\displaystyle{ T }[/math] is the complexity of the comparison.
Proof: Obviously, the variant is correct. So, the lengths of [math]\displaystyle{ S_1' }[/math] and [math]\displaystyle{ S_2' }[/math] are at most [math]\displaystyle{ \lceil1/2\rceil }[/math] of the length of [math]\displaystyle{ S' }[/math]. Consequently, the lengths of [math]\displaystyle{ S_1' }[/math] and [math]\displaystyle{ S_2' }[/math] are at least [math]\displaystyle{ \lfloor1/2\rfloor }[/math] of the length of [math]\displaystyle{ S' }[/math]. In summary, the overall recursion depth is in [math]\displaystyle{ \Theta(\log n) }[/math] in the best and worst case. Next consider the run time of a single recursive call, which receives some [math]\displaystyle{ S' }[/math] as input and calls Mergesort recursively with two subsequences [math]\displaystyle{ S_1' }[/math] and [math]\displaystyle{ S_2' }[/math]. The run time of this recursive call (excluding the run times of the recursive calls with [math]\displaystyle{ S_1' }[/math] and [math]\displaystyle{ S_2' }[/math]) is linear in the length of [math]\displaystyle{ S' }[/math]. Since all recursive calls on the same recursion level operate on pairwise disjoint subsequences, the total run time of all calls on the same recursive level is linear in the length of the original sequence.
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
}
}