归并排序
void Sort(vector<int>& _v)
{
vector<int> v(_v);
int n = v.size();
int ret = 1;
vector<int> temp(n);
while (ret < n)
{
for (int i = 0; i < n; i += 2 * ret)
{
int begin1 = i, end1 = i + ret - 1;
int begin2 = i + ret, end2 = i + 2 * ret - 1;
if (end1 >= n)continue;
if (end2 >= n)end2 = n - 1;
int num = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (v[begin1] <= v[begin2]) temp[num++] = v[begin1++];
else temp[num++] = v[begin2++];
}
while (begin1 <= end1)temp[num++] = v[begin1++];
while (begin2 <= end2)temp[num++] = v[begin2++];
copy(temp.begin() + i, temp.begin() + end2 + 1, v.begin() + i);
}
ret *= 2;
}
for (auto& i : v)
{
_v.emplace_back(i);
}
}
void Sort(vector<int>& _v)
{
vector<int> v(_v);
int n = v.size();
int ret = 1;
vector<int> temp(n);
while (ret < n)
{
for (int i = 0; i < n; i += 2 * ret)
{
int begin1 = i, end1 = i + ret - 1;
int begin2 = i + ret, end2 = i + 2 * ret - 1;
if (end1 >= n)continue;
if (end2 >= n)end2 = n - 1;
int num = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (v[begin1] <= v[begin2]) temp[num++] = v[begin1++];
else temp[num++] = v[begin2++];
}
while (begin1 <= end1)temp[num++] = v[begin1++];
while (begin2 <= end2)temp[num++] = v[begin2++];
copy(temp.begin() + i, temp.begin() + end2 + 1, v.begin() + i);
}
ret *= 2;
}
for (auto& i : v)
{
_v.emplace_back(i);
}
}