Advertisement
Guest User

Untitled

a guest
Mar 18th, 2019
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.64 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template <class I>
  5. void Mergesort(unsigned int begin, unsigned int end, vector<I> &container) {
  6.     /*
  7.         Generic Mergesort for vectors
  8.         unsigned int begin: index of first element
  9.         unsigned int end: index of last element
  10.     */
  11.  
  12.     if (begin == end) {
  13.         // Stop Divide Condition
  14.         return;
  15.     }
  16.  
  17.     // Sort subcontainer
  18.     unsigned int mid = (begin + end) / 2;
  19.     Mergesort(begin, mid, container);
  20.     Mergesort(mid + 1, end, container);
  21.  
  22.     // Subcontainer for merging
  23.     unsigned int left_index_ptr = begin;
  24.     unsigned int right_index_ptr = mid + 1;
  25.     vector<I> merged_container;
  26.  
  27.     while (left_index_ptr <= mid && right_index_ptr <= end) {
  28.         if (container[left_index_ptr] <= container[right_index_ptr]) {
  29.             // Left element is less (or equal to) than right element
  30.             // Take left element
  31.             merged_container.push_back(container[left_index_ptr++]);
  32.         } else {
  33.             // Right element is less than left element
  34.             // Take right element
  35.             merged_container.push_back(container[right_index_ptr++]);
  36.         }
  37.     }
  38.  
  39.     // If index has not reached the end
  40.     while (left_index_ptr <= mid) {
  41.         merged_container.push_back(container[left_index_ptr++]);
  42.     }
  43.     while (right_index_ptr <= end) {
  44.         merged_container.push_back(container[right_index_ptr++]);
  45.     }
  46.  
  47.     // Overwrite part of container with merged_container
  48.     copy(merged_container.begin(), merged_container.end(), container.begin() + begin);
  49. }
  50.  
  51. int main() {
  52.     int buffer;
  53.     vector<int> numbers;
  54.     while (cin >> buffer) {
  55.         numbers.push_back(buffer);
  56.     }
  57.  
  58.     Mergesort(0, numbers.size() - 1, numbers);
  59.  
  60.     for (auto &x : numbers) {
  61.         cout << x << ' ';
  62.     }
  63.     cout << endl;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement