Seite auf deutsch Seite auf deutsch

Mergesort

Mergesort is a very efficient sorting routine, which is patterned after the "divide and conquer"-principle and thus strongly relies on recursion.


Legend:
pink: greater value in current comparison
red: smaller value in current comparison
yellow: pivot element
orange: the part that is already sorted
blue: animation running

The idea is the following:
  1. If the array contains less than two items, we are finished.
  2. Otherwise we split the array into two equal-sized halves over and over and again recursively, until the subarrays under consideration have size 1;
  3. Then we join two subarrays, where each subarray is sorted individually, into a large subarray, which is sorted entirely. This is the "merging" step.
The following example illustrates what happens during the merge step.

The running time can be determined as follows: We have just seen that merging two individually sorted subarrays into an array of length n takes exactly n comparisons. This gives a recurrent equation for the number of comparisons V(n) needed to sort an array of length n, which roughly looks as follows:

V(n) = 2 V(n/2) + n

In order to sort an array of length n, Merge Sort recurs into two subarrays of (roughly) length n/2. After the two subarrays are sorted using V(n/2) comparisons each, we need to merge the two individually sorted subarrays into an array of length n. The merging step costs n comparisons. This recursive equation can be solved mathematically, giving a solution in O(n log n). Observe that the recurrent equation is the same for each input array. Thus the running time is O(n log n), in the best case as well as in the worst case.

References:

An exact analysis of the number of comparisons is found for example (in German) in:
"Steger, Angelika: Diskrete Strukturen. Band 1; Kap.4.1.1"

Weblinks on Merge Sort:



back to the start page

Valid XHTML 1.0!