c++ Merge Sort

Merge Sort

The merge sort combines two sorted arrays into
one larger sorted array.
As the diagram at the left shows,
Array A and Array B merge to form Array C.

Arrays to be merged MUST be SORTED FIRST!!

Be sure to declare Array C in main( ) and establish its size.

Example: Ascending Order
Array A: {7. 12}
Array B: {5, 7, 8}
Array C: {5, 7, 7, 8, 12} after merge

Here is how it works: The first element of array A is compared with the first element of array B. If the first element of array A is smaller than the first element of array B, the element from array A is moved to the new array C. The subscript of array A is now increased since the first element is now set and we move on.

If the element from array B should be smaller, it is moved to the new array C. The subscript of array B is increased. This process of comparing the elements in the two arrays continues until either array A or array B is empty. When one array is empty, any elements remaining in the other (non-empty) array are "pushed" into the end of array C and the merge is complete.

//Function to merge two pre-sorted arrays
void MergeSort(apvector &arrayA, apvector &arrayB, apvector &arrayC)
{
int indexA = 0; // initialize variables for the subscripts
int indexB = 0;
int indexC = 0;

while((indexA < arrayA.length( )) && (indexB < arrayB.length( ))
{
if (arrayA[indexA] < arrayB[indexB])
{
arrayC[indexC] = arrayA[indexA];
indexA++; //increase the subscript
}
else
{
arrayC[indexC] = arrayB[indexB];
indexB++; //increase the subscript
}
indexC++; //move to the next position in the new array
}
// Move remaining elements to end of new array when one merging array is empty
while (indexA < arrayA.length( ))
{
arrayC[indexC] = arrayA[indexA];
indexA++;
indexC++;
}
while (indexB < arrayB.length( ))
{
arrayC[indexC] = arrayB[indexB];
indexB++;
indexC++;
}
return;
}