changed 3 years ago  
Linked with GitHub

Merge Sort (合併排序)

Iterator Ver.














void merge_sort(auto l, auto r) { // [l, r)
	if (distance(l, r) < 2) return;
	auto mid = l + distance(l, r) / 2;
	vector<int> lsub(l, mid), rsub(mid, r);
	merge_sort(lsub.begin(), lsub.end());
	merge_sort(rsub.begin(), rsub.end());
	auto lpt = lsub.begin();
	auto rpt = rsub.begin();
	while (lpt != lsub.end() && rpt != rsub.end())
		*l++ = (*lpt < *rpt ? *lpt++ : *rpt++);
	while (lpt != lsub.end()) *l++ = *lpt++;
	while (rpt != rsub.end()) *l++ = *rpt++;
}

Array Ver.













void merge_sort(int a[], int n) {
	if (n < 2) return;
	int len1 = n / 2, len2 = n - len1;
	int *a1 = a, *a2 = a + len1;
	merge_sort(a1, len1), merge_sort(a2, len2);
	int tmp[n], len = 0, p1 = 0, p2 = 0;
	while (len < n) {
		if (p2 == len2 || (p1 < len1 && a1[p1] <= a2[p2])) tmp[len++] = a1[p1++];
		else tmp[len++] = a2[p2++];
	}
	for (int i = 0; i < n; i++) a[i] = tmp[i];
}

Select a repo