Mergesort

Mergesort (merge of English, merge ' and sort, sort ') is a stable sorting algorithm, the parts according to the principle and rule works. He was first introduced in 1945 by John von Neumann.

Operation

Mergesort considers the data to be sorted as a list and breaks them down into smaller lists, each sorted for himself. The sorted lists are then placed in small zip on major lists together ( engl. (to) merge) until a sorted Total list is reached. The method does not in-place working with arrays in general, there are but ( tricky ) implementations are known in which the sub - arrays are usually merged recursively. Linked lists are particularly suitable for implementation of mergesort, while the in-place sorting order is almost self-

Illustrating the operation

The picture illustrates the three essential steps of a divide-and -conquer method, as implemented in the context of mergesort. The part - trivial step is shown ( the data is divided simply into two halves ). The main work is done in the merging (merge) - so stirred also the name of the algorithm. In contrast, the Parts quicksort step is complicated and the Merge step easier ( namely, a concatenation ).

When considering the method shown in the diagram but you should make people aware that this is only one of several levels of recursion. For instance, could the sort function, which is to sort the two parts 1 and 2, come to the conclusion that these parts are still too big for the sort. Both parts were then divided again and the sorting pass recursively, so that a further recursion is opened, which executes the same steps. In the extreme case ( the case even mergesort is the normal case ) the splitting is so far continued until the two parts consist only of individual data elements.

Implementation

The following pseudo code illustrates the operation of the algorithm, wherein the list to be sorted elements.

Function mergesort ( list);    if (size of list < = 1) then answer list    otherwise        halving the list in the left list, right list        left = mergesort list (left list)        right = mergesort list (right list)        reply merge ( left list, right -list) function merge ( left list, right -list);     new list     while ( list left and right list is not empty )     | If (first element of the left-hand list < = first element of the right-hand list)     | Then add first element on the left list to the new list at the back and remove it from left list     | Otherwise add first element on the right list to the new list at the back and remove it from the right list     solange_ende     while (left list is not empty )     | Add first element on the left list to the new list at the back and remove it from left list     solange_ende     while (right list is not empty )     | Add first element on the right list to the new list at the back and remove it from the right list     solange_ende     reply new list example

In the final merge step, the zipper method is indicated when mixing. Blue arrows illustrate the partitioning step, the green arrows mixing steps.

Complexity

Mergesort is in contrast to quicksort stable when the merge step is implemented correctly. Its complexity ( worst, best and average-case behavior) is in the Landau notation always expressed. This mergesort is superior in complexity the Quicksort certain extent, as the quicksort ( without special precautions ) has a worst-case behavior. However, the probability that this occurs is so small that Quicksort better results in practice.

The recursion formula applies for the duration of merge sort for n elements to sort

With Recursion.

After the master theorem, the Rekursionformel can be approximated by or with each of the solution ( 2 nd case of Mastertheorems, qv)

Correctness and termination

The recursion is the termination of mergesort obviously safe, so that only the correctness yet to be shown. This is done by proving the following assertion:

Claim: In recursion, the sorted sublists of recursion are sorted correctly.

Proof: Let wlog the -th recursion the deepest. Then, the partial lists are obviously sorted as they are singleton. Thus, a part of the assertion is ever saved. Now these sorted sublists are passed a recursion upwards, ie in the -th recursion. There they are sorted correctly on the design of the mixing procedure of mergesort. Thus our assertion is true and proved the total correctness of mergesort.

Natural mergesort

Natural mergesort (natural mergesort ) is an extension of mergesort that are already pre-sorted subsequences, called runs, exploits within the boot list to be sorted. The basis for the merge process here not form the recursive or iterative gained two groups, but to be determined in a first passage runs:

Start list: 3 - 4 - 2 - 1 - 7 - 5 - 8 - 9 - 0-6 Runs determine: 3 - 4 2 1 - 7 5 - 8 - 9 0-6 Merge: 2 - 3 - 4 1-5 - 7 - 8 - 9 0-6 Merge: 1 - 2 - 3 - 4 - 5 - 7 - 8 - 9 0-6 Merge: 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 This variant has the advantage that sorted Follow "recognized" be and is the complexity in the best case. Average and worst -case behavior, however, do not change.

In addition, mergesort is well suited for larger amounts of data that can no longer be kept in main memory - it must only during mixing in each level two lists from the external buffer memory read ( eg hard disk ) and placed into it. A variant uses the available memory better ( and minimizes write accesses to the hard drive), by more than two sub - lists are combined simultaneously, and thus decreases the level of recursion.

Others

Because mergesort the start list as well as all intermediate lists executes sequentially, it is particularly suitable for sorting linked lists. For arrays usually a temporary array of the same length of the array to sort as an intermediate memory is used (ie, merge sort usually does not work in-place, above). Quicksort, however, requires a temporary array. The SGI implementation of the Standard Template Library (STL ) are used as the mergesort algorithm for stable sorting.