• Home
• Contact

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).

• additional memory required, $O(n)$
• good for external sorting
• optimal for linear lists
• stable, if merging is stable

Algorithm

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))$