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: }