Question

Programming with C++ language.

Write and test a version of mergeSort using the following outline:

Merge sort separates the array into 2 parts, sorts them and then uses a temporary array to merge them. Merge sort does its job recursively.

MergeSort(A, upper, lower)

if upper = lower then

     return

else

     middle := (upper + lower) / 2

     MergeSort(A, lower, middle)

     MergeSort(A, middle + 1, upper)

     Merge(A, lower, middle, upper)

end if

end MergeSort

Merge is non-recursive but is more complex than MergeSort because it has 3 jobs to do. The first job copies in order as many elements as it can from the lower and upper halves of the array to the temporary array. The second and third jobs are mutually exclusive. The second job copies the elements remaining in the lower half of the array to the temporary array. These elements are in order and are greater than the elements in the temporary array. The third job does the same things that the second job does but it does them to the upper half of the array. After Merge does two of the three jobs (it always does the first job and does exactly one of the second or third jobs), it copies the temporary array to the correct positions in the array.

The first loop does the first job; the second loop does the second job and the third loop does the third job. Why are the second and third jobs mutually exclusive? Look at the 3 loops’ loop conditions.

Merge(A, lower, middle, upper)

n := upper – lower + 1

B := createArray(n)

pos := 0

left := lower

right := middle + 1

while left <= middle and right <= upper

    if A[left] < A[right] then

       B[pos] := A[left]

       left := left + 1

    else

       B[pos] := A[right]

       right := right + 1   

    end if

    pos := pos + 1

end while

while left <= middle

    B[pos] := A[left]

    left := left + 1

    pos := pos + 1

end while

while right <= upper

    B[pos] := A[right]

    right := right + 1

    pos := pos + 1

end while

for pos := 0 to n – 1

    A[pos + lower] := B[pos]

end for

end Merge

It is not necessary to create B in Merge. We can create B as either a global, module, or class level variable.

Answer 1

#include <iostream>
using namespace std;
#define MAX 10000
void merge(int array[],int low,int mid,int high )
{
   int temp[MAX];
   int i = low;
   int j = mid +1 ;
   int k = low ;

   while( (i <= mid) && (j <=high) )
   {
       if(array[i] <= array[j])
           temp[k++] = array[i++] ;
       else
           temp[k++] = array[j++] ;
   }
  
   while( i <= mid )
       temp[k++]=array[i++];
  
   while( j <= high )
       temp[k++]=array[j++];

   for(i= low; i <= high ; i++)
       array[i]=temp[i];
  
}

void merge_sort( int array[],int low, int high )
{
   int mid;
   if( low != high )
   {
       mid = (low+high)/2;
       merge_sort( array,low , mid );
       merge_sort( array,mid+1, high );
       merge( array,low, mid, high );
   }
}

int main()
{
   int i,n;
   int array[MAX];
   cout<<"Enter the number of elements : ";
   cin>>n;
   cout<<"Enter elements to be sorted : ";
   for(i=0;i<n;i++)
   {
       cin>>array[i];
   }
   merge_sort( array,0, n-1);
   cout<<"Sorted list is :\n";
   for( i = 0 ; i<n ; i++)
       cout<<array[i]<<" ";
   return 0;
}