/**
* Merge Sort using N/2 temporary storage.
* @see http://e...content-available-to-author-only...a.org/wiki/Merge_sort#Analysis
*
* Author: Erel Segal
* Created: 2010-10-17
*/
#include <vector>
#include <iostream>
using namespace std;
template <class T> void swap ( T& a, T& b ) {
T c(a); a=b; b=c;
}
/* Sort the given array in the range [iFrom,iTo), using a temporary storage starting at iTemp */
template <class Iterator> void merge_sort(Iterator iFrom, Iterator iTo, Iterator iTemp) {
if (iTo <= iFrom+1)
return;
// recursively sort each half seperately:
size_t diff = (iTo-iFrom);
//cout << "merge_sort " << diff << " elements: " << *iFrom << ".." << *(iTo-1) << endl;
Iterator iMiddle = iFrom+diff/2;
merge_sort(iFrom, iMiddle, iTemp);
merge_sort(iMiddle, iTo, iTemp);
// merge the two halves using the temporary storage:
/// a. move the smaller array to the temporary storage:
Iterator iLeft, iOutput;
for (iLeft=iFrom, iOutput=iTemp; iLeft<iMiddle; ++iLeft, ++iOutput)
*iOutput = *iLeft;
Iterator iTempEnd = iOutput;
/// b. merge the smaller array from the temp storage to the main array:
Iterator iRight;
for (iOutput=iFrom, iLeft=iTemp, iRight=iMiddle; iLeft<iTempEnd && iRight<iTo;) {
//cout << "comparing " << *iLeft << " and " << *iRight;
if (*iLeft <= *iRight) {
*iOutput = *iLeft;
++iLeft;
} else {
*iOutput = *iRight;
++iRight;
}
//cout << "; putting " << *iOutput << endl;
++iOutput;
}
for (; iLeft<iTempEnd; ) {
*iOutput = *iLeft;
++iLeft;
++iOutput;
}
for (; iRight<iTo; ) {
*iOutput = *iRight;
++iRight;
++iOutput;
}
}
template <class T> void merge_sort(vector<T>& array) {
vector<T> temp(array.size()/2); // temporary vector for merging
merge_sort(array.begin(), array.end(), temp.begin());
}
#include <stdlib.h>
#include <time.h>
int main() {
srand(time(NULL));
int num;
vector<int> numbers;
while (1) {
cin >> num;
if (cin.eof()) break;
if (num==0) // 0 means "choose at random"
num = rand()%100;
numbers.push_back(num);
}
cout << endl << "before sort: ";
for (size_t i=0; i<numbers.size(); ++i) cout << numbers[i] << " ";
merge_sort(numbers);
cout << endl << "after sort: ";
for (size_t i=0; i<numbers.size(); ++i) cout << numbers[i] << " ";
}
LyoqCiAqIE1lcmdlIFNvcnQgdXNpbmcgTi8yIHRlbXBvcmFyeSBzdG9yYWdlLgogKiBAc2VlIGh0dHA6Ly9lLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5hLm9yZy93aWtpL01lcmdlX3NvcnQjQW5hbHlzaXMKICoKICogQXV0aG9yOiBFcmVsIFNlZ2FsCiAqIENyZWF0ZWQ6IDIwMTAtMTAtMTcKICovCgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0ZW1wbGF0ZSA8Y2xhc3MgVD4gdm9pZCBzd2FwICggVCYgYSwgVCYgYiApIHsKICBUIGMoYSk7IGE9YjsgYj1jOwp9CgoKLyogU29ydCB0aGUgZ2l2ZW4gYXJyYXkgaW4gdGhlIHJhbmdlIFtpRnJvbSxpVG8pLCB1c2luZyBhIHRlbXBvcmFyeSBzdG9yYWdlIHN0YXJ0aW5nIGF0IGlUZW1wICAqLwp0ZW1wbGF0ZSA8Y2xhc3MgSXRlcmF0b3I+IHZvaWQgbWVyZ2Vfc29ydChJdGVyYXRvciBpRnJvbSwgSXRlcmF0b3IgaVRvLCBJdGVyYXRvciBpVGVtcCkgewogIGlmIChpVG8gPD0gaUZyb20rMSkKICAgIHJldHVybjsKCiAgLy8gcmVjdXJzaXZlbHkgc29ydCBlYWNoIGhhbGYgc2VwZXJhdGVseToKICBzaXplX3QgZGlmZiA9IChpVG8taUZyb20pOwogIC8vY291dCA8PCAibWVyZ2Vfc29ydCAiIDw8IGRpZmYgPDwgIiBlbGVtZW50czogIiA8PCAqaUZyb20gPDwgIi4uIiA8PCAqKGlUby0xKSA8PCBlbmRsOwogIEl0ZXJhdG9yIGlNaWRkbGUgPSBpRnJvbStkaWZmLzI7CgogIG1lcmdlX3NvcnQoaUZyb20sIGlNaWRkbGUsIGlUZW1wKTsKICBtZXJnZV9zb3J0KGlNaWRkbGUsIGlUbywgaVRlbXApOwoKCiAgLy8gbWVyZ2UgdGhlIHR3byBoYWx2ZXMgdXNpbmcgdGhlIHRlbXBvcmFyeSBzdG9yYWdlOgoKICAvLy8gYS4gbW92ZSB0aGUgc21hbGxlciBhcnJheSB0byB0aGUgdGVtcG9yYXJ5IHN0b3JhZ2U6CiAgSXRlcmF0b3IgaUxlZnQsIGlPdXRwdXQ7CiAgZm9yIChpTGVmdD1pRnJvbSwgaU91dHB1dD1pVGVtcDsgaUxlZnQ8aU1pZGRsZTsgKytpTGVmdCwgKytpT3V0cHV0KQogICAgKmlPdXRwdXQgPSAqaUxlZnQ7CiAgSXRlcmF0b3IgaVRlbXBFbmQgPSBpT3V0cHV0OwoKICAvLy8gYi4gbWVyZ2UgdGhlIHNtYWxsZXIgYXJyYXkgZnJvbSB0aGUgdGVtcCBzdG9yYWdlIHRvIHRoZSBtYWluIGFycmF5OgogIEl0ZXJhdG9yIGlSaWdodDsKICBmb3IgKGlPdXRwdXQ9aUZyb20sIGlMZWZ0PWlUZW1wLCBpUmlnaHQ9aU1pZGRsZTsgaUxlZnQ8aVRlbXBFbmQgJiYgaVJpZ2h0PGlUbzspIHsKICAgIC8vY291dCA8PCAiY29tcGFyaW5nICIgPDwgKmlMZWZ0IDw8ICIgYW5kICIgPDwgKmlSaWdodDsKICAgIGlmICgqaUxlZnQgPD0gKmlSaWdodCkgewogICAgICAqaU91dHB1dCA9ICppTGVmdDsKICAgICAgKytpTGVmdDsKICAgIH0gZWxzZSB7CiAgICAgICppT3V0cHV0ID0gKmlSaWdodDsKICAgICAgKytpUmlnaHQ7CiAgICB9CiAgICAvL2NvdXQgPDwgIjsgcHV0dGluZyAiIDw8ICppT3V0cHV0IDw8IGVuZGw7CiAgICArK2lPdXRwdXQ7CiAgfQoKICBmb3IgKDsgaUxlZnQ8aVRlbXBFbmQ7ICkgewogICAgKmlPdXRwdXQgPSAqaUxlZnQ7CiAgICArK2lMZWZ0OwogICAgKytpT3V0cHV0OwogIH0KCiAgZm9yICg7IGlSaWdodDxpVG87ICkgewogICAgKmlPdXRwdXQgPSAqaVJpZ2h0OwogICAgKytpUmlnaHQ7CiAgICArK2lPdXRwdXQ7CiAgfQp9CgoKdGVtcGxhdGUgPGNsYXNzIFQ+IHZvaWQgbWVyZ2Vfc29ydCh2ZWN0b3I8VD4mIGFycmF5KSB7CiAgdmVjdG9yPFQ+IHRlbXAoYXJyYXkuc2l6ZSgpLzIpOyAgLy8gdGVtcG9yYXJ5IHZlY3RvciBmb3IgbWVyZ2luZwogIG1lcmdlX3NvcnQoYXJyYXkuYmVnaW4oKSwgYXJyYXkuZW5kKCksIHRlbXAuYmVnaW4oKSk7Cn0KCgoKI2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8dGltZS5oPgppbnQgbWFpbigpIHsKICBzcmFuZCh0aW1lKE5VTEwpKTsgCiAgaW50IG51bTsKICB2ZWN0b3I8aW50PiBudW1iZXJzOwogIHdoaWxlICgxKSB7CiAgICBjaW4gPj4gbnVtOwogICAgaWYgKGNpbi5lb2YoKSkgYnJlYWs7CiAgICBpZiAobnVtPT0wKSAgLy8gMCBtZWFucyAiY2hvb3NlIGF0IHJhbmRvbSIKICAgICAgbnVtID0gcmFuZCgpJTEwMDsKICAgIG51bWJlcnMucHVzaF9iYWNrKG51bSk7CiAgfQoKICBjb3V0IDw8IGVuZGwgPDwgImJlZm9yZSBzb3J0OiAiOwogIGZvciAoc2l6ZV90IGk9MDsgaTxudW1iZXJzLnNpemUoKTsgKytpKSBjb3V0IDw8IG51bWJlcnNbaV0gPDwgIiAiOwogIG1lcmdlX3NvcnQobnVtYmVycyk7CiAgY291dCA8PCBlbmRsIDw8ICJhZnRlciBzb3J0OiAiOwogIGZvciAoc2l6ZV90IGk9MDsgaTxudW1iZXJzLnNpemUoKTsgKytpKSBjb3V0IDw8IG51bWJlcnNbaV0gPDwgIiAiOwp9Cg==