Return to Topic Menu | Computer Science Main Page | MathBits.com | Terms of Use | Resource CD  

 

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 <int> &arrayA, apvector <int> &arrayB, apvector <int> &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;
}