Dmitry Rudakov
54 lines
1.2 KiB
C++
54 lines
1.2 KiB
C++
#pragma once
|
|
|
|
#include <deque>
|
|
|
|
template<class T, class Comp>
|
|
std::deque<T> Merge(const std::deque<T>& half1, const std::deque<T>& half2, const Comp& comparator) {
|
|
std::deque<T> result;
|
|
auto it1 = half1.begin();
|
|
auto it2 = half2.begin();
|
|
|
|
while (it1 != half1.end() && it2 != half2.end()) {
|
|
if (!comparator(*it2, *it1)) {
|
|
result.push_back(*it1);
|
|
++it1;
|
|
} else {
|
|
result.push_back(*it2);
|
|
++it2;
|
|
}
|
|
}
|
|
|
|
while (it1 != half1.end()) {
|
|
result.push_back(*it1);
|
|
++it1;
|
|
}
|
|
|
|
while (it2 != half2.end()) {
|
|
result.push_back(*it2);
|
|
++it2;
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
template<class T, class Comp>
|
|
std::deque<T> MergeSort(const std::deque<T>& src, const Comp& comparator) {
|
|
if (src.size() <= 1) {
|
|
return src;
|
|
}
|
|
|
|
const size_t mid = src.size() / 2;
|
|
const auto mid_it = std::next(src.begin(), mid);
|
|
|
|
const auto left = MergeSort(
|
|
std::deque<T>(src.begin(), mid_it),
|
|
comparator
|
|
);
|
|
const auto right = MergeSort(
|
|
std::deque<T>(mid_it, src.end()),
|
|
comparator
|
|
);
|
|
|
|
return Merge(left, right, comparator);
|
|
}
|