 |
The merge sort combines two
sorted lists into
one larger sorted list.
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.
At this time, the index of array A is increased since the first element is no
longer of concern.
If the element from array B should be smaller, it is moved to
the new array C. The increment of array B is then increased.
This process of comparing elements continues until one of the "feeder" arrays is
empty.
When this occurs, the remaining elements in the other array are "pushed" into
the end of array C to complete the merge.
//Function to merge two pre-sorted arrays
void merge_sort(apvector <int> &arrayA, apvector <int> &arrayB, apvector <int> &arrayC)
{
int indexA = 0;
// initialize the Array Indices
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 index
}
else
{
arrayC[indexC] = arrayB[indexB];
indexB++; //increase the index
}
indexC++;
//move to the next position in the new array
}
// Push remaining elements to end of new array
when 1 feeder array is empty
while (indexA < arrayA.length( ))
{
arrayC[indexC] = arrayA[indexA];
indexA++;
indexC++;
}
while (indexB < arrayB.length( ))
{
arrayC[indexC] = arrayB[indexB];
indexB++;
indexC++;
}
return;
}
|
