Question

Implement a version of merge() that copies the second half of a[] to aux[] in decreasing order and then does the merge back to a[]. This change allows you to remove the code to test that each of the halves has been exhausted from the inner loop. Note: the resulting sort is not stable.

Algorithms Fourth Edition Exercise 2.2.10

Answer 1

void merge(int a[],int init,int final,int mid)

{

    int pointer1=init;

    int pointer2=final;

    int aux[final-mid+1];

    int aux2[final-init+1];

    int pointer3=0;

    for(int x=final;x>=mid;x--)

   {

        aux[pointer3++]=a[x];

}

   j=0;

   int sol_pt=0;

   while(i<mid && j<pointer3)

   {

         if(a[i]<aux[j])

        {

              aux2[sol_pt++]=a[i];

              i++;

        }

        else

        {

            aux2[sol_pt++]=aux[j];

             j++;

        }

}

while(i<mid)

{

      aux2[sol_pt++]=a[i];

       i++;

}

while(j<pointer3)

{

    aux2[sol_pt++]=aux[j];

     j++;

}

for(int k=0;k<pointer3;k++)

{

      a[init+k]=aux2[k];

}

}