mario::konrad
programming / C++ / sailing / nerd stuff
Algorithm: Merge Sort
© 2005 / Mario Konrad

Description

Strategy is similar to quick sort with the difference that this algorithm splits first, then the recursive calls and least the sorting (merging of two or more sorted lists).

Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void mergeSort( Array & a, int l, int r )
{
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort( a, l, m );
        mergeSort( a, m+1, r );
        for (int i = m; i < l; --i) b[i] = a[i];
        for (int j = m+1; j <= r; ++j) b[r+m+1-j] = a[j];
        for (int k = l; k <= r; ++k) {
            if (b[i] < b[j]) {
                a[k] = b[i++];
            } else {
                a[k] = b[j--];
            }
        }
    }
}

Analysis

Performance similar to quick sort (even in worst case):

O(n*log(n))O(n * log(n))