Mergesort

Merge sort

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.

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
		}
	}