---
tags: codebook
---

{%hackmd theme-dark %}

# merge sort(subscript)

#include<iostream>
#include<vector>
using namespace std;
//額外空間版本O(nlogn)+M(n)
void merge_sort(vector<long long>&v, size_t l, size_t r) {
//終止條件
	if (r - l < 2) return;
//分割split
	size_t mid = (l + r) / 2;
	vector<long long> lsub(v.begin() + l, v.begin() + mid);
	vector<long long> rsub(v.begin() + mid, v.begin() + r);
//遞迴recursion
	merge_sort(lsub, 0, lsub.size());
	merge_sort(rsub, 0, rsub.size());
//歸併merge
	size_t lpivot = 0, rpivot = 0;
	while (lpivot != lsub.size() && rpivot != rsub.size()) {
		if (lsub[lpivot] < rsub[rpivot])
			v[l] = lsub[lpivot], l++, lpivot++;
		else
			v[l] = rsub[rpivot], l++, rpivot++;
	}
	while (lpivot != lsub.size())
		v[l] = lsub[lpivot], l++, lpivot++;
	while (rpivot != rsub.size())
		v[l] = rsub[rpivot], l++, rpivot++;

}
int main() {
	vector<long long> vec{1, 5, 4, 2, 0, 3, 7, 6, 9, 8};
	merge_sort(vec, 0, vec.size());
	for (vector<long long>::iterator i = vec.begin(); i != vec.end(); i++)
		cout << *i << ' ';
	return 0;
}