С++ Сортировка слиянием
Отсортируйте данный массив, используя сортировку слиянием. Попробуйте написать свою реализацию, например, не создавая новые векторы при каждом рекурсивном вызове.
Входные данные
Первая строка входных данных содержит количество элементов в массиве N,N≤105. Далее идут N целых чисел, не превосходящих по абсолютной величине 109.
Выходные данные
Выведите эти числа в порядке неубывания.
Примеры
Ввод
Вывод
2
3 1
1 3
#include <vector>
#include<iostream>
template <typename T>
inline void swap(T& arg1, T& arg2)
{
T temp = arg1;
arg1 = arg2;
arg2 = temp;
};
template <typename T>
inline void merge(std::vector<T>& vArray, std::vector<T>& vTemp, int head, int middle, int tail)
{
int tmp = 0, lower = head, upper = middle + 1;
while (lower <= middle && upper <= tail)
{
if (vArray[lower] < vArray[upper])
{
vTemp[tmp++] = vArray[lower++];
}
else
{
vTemp[tmp++] = vArray[upper++];
}
}
if (lower <= middle)
{
for (; lower <= middle; vTemp[tmp++] = vArray[lower++]);
}
else
{
for (; upper <= tail; vTemp[tmp++] = vArray[upper++]);
}
int arrayPointer = head;
for (tmp = 0; arrayPointer <= tail; vArray[arrayPointer++] = vTemp[tmp++]);
}
template <typename T>
inline void merge_sort_helper(std::vector<T>& vArray, std::vector<T>& vTemp, int head, int tail)
{
if (head == tail)
{
return;
}
int middle = (head + tail) / 2;
merge_sort_helper(vArray, vTemp, head, middle);
merge_sort_helper(vArray, vTemp, middle + 1, tail);
merge(vArray, vTemp, head, middle, tail);
}
template <typename T>
void merge_sort(std::vector<T>& vArray)
{
std::vector<T> v(vArray.size(), 0);
merge_sort_helper(vArray, v, 0, vArray.size() - 1);
}
int main() {
int n;
std::cin >> n;
std:: vector<int>vArray(n);
for (int i = 0; i < n; i++) {
std:: cin >> vArray[i];
}
merge_sort(vArray);
for (int i = 0; i < n; i++) {
std::cout << vArray[i]<<" ";
}
}