# Untitled

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)
}```