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