マージソート
概要
高速な安定ソートです．静的に大きめの作業領域を確保しています．詳しい説明はそこら中にあるのでググってください．
計算量
$\Theta(n \log n)$
実装
template <typename T>
void mergesort(T *l, T *r) {
int n = r - l;
static T tmp[1000010];
auto merge = [](T *l1, T *r1, T *l2, T *r2, T *dst) {
while (l1 != r1 && l2 != r2) {
if (*l1 < *l2)
*dst++ = *l1++;
else
*dst++ = *l2++;
}
while (l1 != r1) *dst++ = *l1++;
while (l2 != r2) *dst++ = *l2++;
};
for (int w = 2; w / 2 < n; w <<= 1) {
for (int i = 0; i < n; i += w) {
merge(l + i, min(l + i + w / 2, l + n), min(l + i + w / 2, l + n),
min(l + i + w, l + n), tmp + i);
}
for (int i = 0; i < n; i++) l[i] = tmp[i];
}
}