programming / C++ / sailing / nerd stuff
Algorithm: Merge Sort

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

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