Skip to content

Instantly share code, notes, and snippets.

@agasiev
Created December 26, 2012 13:11
Show Gist options
  • Save agasiev/4380313 to your computer and use it in GitHub Desktop.
Save agasiev/4380313 to your computer and use it in GitHub Desktop.
Merge sort with iterators
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void msort(vector<int>::iterator left, vector<int>::iterator right) {
if (right - left <= 1) return;
msort(left, left + (right - left)/2);
msort(left + (right - left)/2, right);
vector<int> res(right - left);
merge(left, left + (right - left)/2, left + (right - left)/2, right, res.begin());
copy(res.begin(), res.end(), left);
}
int main(int, char**) {
vector<int> a(10);
for (int i = 0; i < a.size(); i++) {
a[i] = 10 - i;
cout << a[i] << " ";
}
cout << endl;
msort(a.begin(), a.end());
for (int i = 0; i < a.size(); i++) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment