    001: #include <iostream>
    002: #include <vector>
    003: #include <cstdlib>
    004: #include <ctime>
    005:
    006: using namespace std;
    007:
    008: #include "ccc_time.cpp"
    009:
    010: /**
    011:    Merges two adjacent ranges in a vector
    012:    @param a the vector with the elements to merge
    013:    @param from the start of the first range
    014:    @param mid the end of the first range
    015:    @param to the end of the second range
    016: */
    017: void merge(vector<int>& a, int from, int mid, int to)
    018: {
    019:    int n = to - from + 1; /* size of the range to be merged */
    020:    /* merge both halves into a temporary vector b */
    021:    vector<int> b(n);
    022:
    023:    int i1 = from;
    024:       /* next element to consider in the first half */
    025:    int i2 = mid + 1;
    026:       /* next element to consider in the second half */
    027:    int j = 0; /* next open position in b */
    028:
    029:    /*
    030:       As long as neither i1 nor i2 past the end, move the smaller
    031:       element into b
    032:    */
    033:    while (i1 <= mid && i2 <= to)
    034:    {
    035:       if (a[i1] < a[i2])
    036:       {
    037:          b[j] = a[i1];
    038:          i1++;
    039:       }
    040:       else
    041:       {
    042:          b[j] = a[i2];
    043:          i2++;
    044:       }
    045:       j++;
    046:    }
    047:
    048:    /*
    049:       Note that only one of the two while loops below is executed
    050:    */
    051:
    052:    /* Copy any remaining entries of the first half */
    053:    while (i1 <= mid)
    054:    {
    055:       b[j] = a[i1];
    056:       i1++;
    057:       j++;
    058:    }
    059:    /* Copy any remaining entries of the second half */
    060:    while (i2 <= to)
    061:    {
    062:       b[j] = a[i2];
    063:       i2++;
    064:       j++;
    065:    }
    066:
    067:    /* Copy back from the temporary vector */
    068:    for (j = 0; j < n; j++)
    069:       a[from + j] = b[j];
    070: }
    071:
    072: /**
    073:    Sorts the elements in a range of a vector.
    074:    @param a the vector with the elements to sort
    075:    @param from start of the range to sort
    076:    @param to end of the range to sort
    077: */
    078: void merge_sort(vector<int>& a, int from, int to)
    079: {
    080:    if (from == to) return;
    081:    int mid = (from + to) / 2;
    082:    /* sort the first and the second half */
    083:    merge_sort(a, from, mid);
    084:    merge_sort(a, mid + 1, to);
    085:    merge(a, from, mid, to);
    086: }
    087:
    088: /**
    089:    Prints all elements in a vector
    090:    @param a the vector to print
    091: */
    092: void print(vector<int> a)
    093: {
    094:    for (int i = 0; i < a.size(); i++)
    095:       cout << a[i] << " ";
    096:    cout << "\n";
    097: }
    098:
    099: /**
    100:    Sets the seed of the random number generator.
    101: */
    102: void rand_seed()
    103: {
    104:    int seed = static_cast<int>(time(0));
    105:    srand(seed);
    106: }
    107:
    108: /**
    109:    Computes a random integer in a range.
    110:    @param a the bottom of the range
    111:    @param b the top of the range
    112:    @return a random integer x, a <= x and x <= b
    113: */
    114: int rand_int(int a, int b)
    115: {
    116:    return a + rand() % (b - a + 1);
    117: }
    118:
    119: int main()
    120: {
    121:    rand_seed();
    122:    cout << "Enter vector size: ";
    123:    int n;
    124:    cin >> n;
    125:    vector<int> v(n);
    126:    for (int i = 0; i < v.size(); i++)
    127:       v[i] = rand_int(1, 100);
    128:    Time before;
    129:    merge_sort(v, 0, v.size() - 1);
    130:    Time after;
    131:
    132:    cout << "Elapsed time = " << after.seconds_from(before)
    133:       << " seconds\n";
    134:    return 0;
    135: }