Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- template <class I>
- void Mergesort(unsigned int begin, unsigned int end, vector<I> &container) {
- /*
- Generic Mergesort for vectors
- unsigned int begin: index of first element
- unsigned int end: index of last element
- */
- if (begin == end) {
- // Stop Divide Condition
- return;
- }
- // Sort subcontainer
- unsigned int mid = (begin + end) / 2;
- Mergesort(begin, mid, container);
- Mergesort(mid + 1, end, container);
- // Subcontainer for merging
- unsigned int left_index_ptr = begin;
- unsigned int right_index_ptr = mid + 1;
- vector<I> merged_container;
- while (left_index_ptr <= mid && right_index_ptr <= end) {
- if (container[left_index_ptr] <= container[right_index_ptr]) {
- // Left element is less (or equal to) than right element
- // Take left element
- merged_container.push_back(container[left_index_ptr++]);
- } else {
- // Right element is less than left element
- // Take right element
- merged_container.push_back(container[right_index_ptr++]);
- }
- }
- // If index has not reached the end
- while (left_index_ptr <= mid) {
- merged_container.push_back(container[left_index_ptr++]);
- }
- while (right_index_ptr <= end) {
- merged_container.push_back(container[right_index_ptr++]);
- }
- // Overwrite part of container with merged_container
- copy(merged_container.begin(), merged_container.end(), container.begin() + begin);
- }
- int main() {
- int buffer;
- vector<int> numbers;
- while (cin >> buffer) {
- numbers.push_back(buffer);
- }
- Mergesort(0, numbers.size() - 1, numbers);
- for (auto &x : numbers) {
- cout << x << ' ';
- }
- cout << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement