Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.2 kB
2
Indexable
Never
void merge(int *arr, const int size, int &compCount, int &moveCount, int first, int mid, int last){
    
    int *tempArray = new int[size];
    // Determine the first, mid, and the last values
    int first1 = first; 	
    int last1 = mid; 		
    int first2 = mid + 1;	
    int last2 = last;		
    int index = first1; 
    
    // Compare each element and start to fill array
    while( ( first1 <= last1) && ( first2 <= last2 ) ){
        if( arr[first1] < arr[first2] ){
            tempArray[index] = arr[first1];
            first1++;
        }
        else{
            tempArray[index] = arr[first2];
            first2++;
        }
        compCount++;
        moveCount++;
        index++;
    }
    
    // Finish to fill the array with one of halves
    while( ( first1 <= last1) ){
        tempArray[index] = arr[first1];
        moveCount++;
        index++;
        first1++;
    }
    
    while( ( first2 <= last2) ){
        tempArray[index] = arr[first2];
        moveCount++;
        index++;
        first2++;
    }
    
    // Copy the temp array into the real array
    for ( index = first; index <= last; index++){
        arr[index] = tempArray[index];
        moveCount++;
    }
    // Delete the temp array 
    delete [] tempArray; 
}

/*
* Overloaded function of mergeSort
* Has 2 extra parameters which is first and last index of the array 
*/
void mergeSort(int *arr, const int size, int &compCount, int &moveCount, int first, int last){
    if ( first < last ) {
        int mid = (first + last)/2; 	
        
        mergeSort(arr, size, compCount, moveCount, first, mid); // Sort the first half

        mergeSort(arr, size, compCount, moveCount, mid + 1, last); // Sort the second half

        // Merge the two halves
        merge(arr, size, compCount, moveCount, first, mid, last);
   }
}
void mergeSort(int *arr, const int size, int &compCount, int &moveCount){
    // Call the overloaded function of mergeSort to be able to add 2 extra parameter
    mergeSort( arr, size, compCount, moveCount, 0, size - 1); // First index is zero, last index is (size - 1) 
}