1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 using namespace std; 6  7 int COMPARE_COUNT = 0; 8  9 void merge_sort(vector
        
          &array, vector
         
           &aux, int lo, int hi)10 {11 if ( lo >= hi )12 return;13 14 int mid = ( hi + lo ) / 2;15 merge_sort(array, aux, lo, mid);16 merge_sort(array, aux, mid + 1, hi);17 18 //vector
          
            aux;19 for ( int i = lo; i < hi +1; ++i )20 aux[i] = array[i];21 22 int i = lo;23 int j = mid + 1;24 int k = lo;25 26 while ( k < hi + 1 )27 {28 if ( i > mid ) array[k++] = aux[j++];29 else if ( j > hi ) array[k++] = aux[i++];30 else if ( aux[i] <= aux[j] ) 31 {32 array[k++] = aux[i++];33 COMPARE_COUNT++;34 }35 else{36 array[k++] = aux[j++];37 COMPARE_COUNT++;38 }39 }40 41 return;42 }43 44 void Print(const vector
           
             &array)45 {46 vector
            
             ::const_iterator _begin = array.begin();47 while ( _begin != array.end() )48 cout<<*_begin++<<" ";49 50 cout<
             
              >size;58 59 vector
              
                array;60 for ( int i = 0; i < size; ++i )61 array.push_back( rand() % size + 1);62 63 cout<<"The shuffling array is:"<
               

aux;67 aux.resize(array.size());68 //aux = array;69 merge_sort(array, aux, 0, size - 1);70 71 cout<<"The sorted array is:"<