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