1 // Taken from https://github.com/mjkloeckner/sav.git 2 3 #include <iostream> 4 #include <vector> 5 6 #define VECTOR_ELEMENT_LIMIT 20 7 8 void vector_random_populate(std::vector<int>& v) { 9 srand (time(NULL)); 10 for(size_t i = 0; i < v.size(); ++i) 11 v[i] = (int)(rand() % VECTOR_ELEMENT_LIMIT); 12 } 13 14 void vector_print(const std::vector<int> v) { 15 std::cout << "["; 16 for(size_t i = 0; i < v.size(); ++i) { 17 std::cout << v[i] << ((v.size() == i+1) ? "" : ", "); 18 } 19 std::cout << "]\n"; 20 } 21 22 void merge(std::vector<int>& v, int low, int middle, int high) { 23 size_t n1, n2, i, j, k; 24 25 n1 = middle - low; 26 n2 = high - middle; 27 28 int B[n1], C[n2]; 29 30 /* B holds middle low array */ 31 for(i = low, j = 0; i < middle; i++, j++) 32 B[j] = v[i]; 33 34 /* C middle high */ 35 for(i = middle, j = 0; i < high; i++, j++) 36 C[j] = v[i]; 37 38 /* merge B and C in order */ 39 for(k = low, i = j = 0; (k < high) && (i < n1) && (j < n2); k++) 40 v[k] = ((B[i] <= C[j]) ? v[k] = B[i++] : C[j++]); 41 42 while(i < n1) 43 v[k++] = B[i++]; 44 45 while(j < n2) 46 v[k++] = C[j++]; 47 } 48 49 50 void merge_sort(std::vector<int>& v, int low, int high) { 51 int middle = ((high + low) / 2); 52 53 if((high - low) > 1) { 54 merge_sort(v, low, middle); 55 merge_sort(v, middle, high); 56 merge(v, low, middle, high); 57 } 58 } 59 60 int main (void) { 61 std::vector<int> v(10); 62 vector_random_populate(v); 63 vector_print(v); 64 merge_sort(v, 0, v.size()); 65 vector_print(v); 66 67 return 0; 68 }
