SHOW:
|
|
- or go back to the newest paste.
| 1 | #include <iostream> | |
| 2 | #include <vector> | |
| 3 | #include <iterator> | |
| 4 | #include <algorithm> | |
| 5 | #include <numeric> | |
| 6 | ||
| 7 | using namespace std; | |
| 8 | ||
| 9 | template <typename It> | |
| 10 | void PrintRange(It range_begin, It range_end) {
| |
| 11 | for (auto it = range_begin; it != range_end; ++it) {
| |
| 12 | cout << *it << " "s; | |
| 13 | } | |
| 14 | cout << endl; | |
| 15 | } | |
| 16 | ||
| 17 | template <typename RandomIt> | |
| 18 | void MergeSort(RandomIt range_begin, RandomIt range_end){
| |
| 19 | if (next(range_begin) == range_end){
| |
| 20 | return; | |
| 21 | } | |
| 22 | vector<typename RandomIt::value_type> elements(range_begin, range_end); | |
| 23 | auto middleof = elements.begin()+ (elements.size()/2); | |
| 24 | MergeSort(elements.begin(), middleof); | |
| 25 | MergeSort(middleof, elements.end()); | |
| 26 | ||
| 27 | vector<typename RandomIt::value_type> v; | |
| 28 | merge(elements.begin(), middleof, middleof, elements.end(), back_inserter(v)); | |
| 29 | swap_ranges(range_begin, range_end, begin(v)); | |
| 30 | } | |
| 31 | ||
| 32 | int main() {
| |
| 33 | vector<int> v = { 6, 4, 7, 6, 4, 4, 0, 1 };
| |
| 34 | MergeSort(begin(v), end(v)); | |
| 35 | for (int x : v) {
| |
| 36 | cout << x << " "; | |
| 37 | } | |
| 38 | cout << endl; | |
| 39 | return 0; | |
| 40 | } | |
| 41 |