merge sort ( a program that will explain the working of whole merge sort )

well today we are going to learn about merge sort i think it is the very first program written in "analysis of algorithm  by coreman "
i am going to tell you the easiest approach. i want you to copy this program in your compiler and let it run... this program will unfold everything.

#include<stdio.h>
#include<conio.h>
void main()
{
     int i,array1[]={1,5,7,84,32,76,41,62,79,13};
     merge(array1,0,9);
    for( i=0;i<=9;i++)
    {
          printf("%d\n",array1[i]);
    }
}

void merge(int *A,int p,int n)
{
  if (p==n)
    {
    return;
    }
  else
   {

    int q=p+(n-p)/2;
    printf("now calling merge(A,%d,%d)\n",p,q);
    merge(A,p,q);
    printf(" now calling merge(A,%d,%d)\n",q+1,n);
    merge(A,q+1,n);
    printf("now calling combine(A,%d,%d,%d)\n",p,q,n);
    combine(A,p,q,n);
   }
}
void combine(int *A,int p,int x,int n)
{
    int i = 0;
    int j=0;
    int n1 = p ;
    int left[10];
    int right[10];
    for( i=0;p<=x;i++,p++)
    {
            left[i] = A[p];
            printf("the element added in left now which is %d",left[i]);

    }
    left[i]=10000;

    for(i=0;(x+1)<=n;x++,i++)
    {
        right[i] = A[x+1];
        printf("the element added in right now which is  %d",right[i]);

    }
    right[i]=50000;
    printf("\n");
    for(i=0,j=0;n1<=n;n1++)
    {
        if(left[i]<right[j])
        {
            A[n1]=left[i];
            printf("the element added from left in A[%d] which is %d \n",n1,A[n1]);
            i++;
        }
        else
        {

            A[n1]= right[j];
            printf("the element added from right in A[%d] which is \n",A[n1]);
            j++;
        }
    }
}

here is the explanation well it is a method to sort numbers by divide and conquer algorithim

the idea is if you have to solve the smaller problems and somehow combine their results to solve the bigger ones

there are lot of techniques also for example dynamic programming and greedy based algo

and this is one among them

here what i am doing .. in order to sort the numbers

i am breaking the problems into smaller parts

as you can see i wrote merge(A,0,9)

i used array1 here

i think

so when i am calling it first it will enter into merge program

*function

not program

and there a smaller version of it would be called ie merge(A,0,2)

in actual i wrote it as merge (a,p,q )

where p is starting point

and q is the point upto which i should

and when it will enter into it it will again divide the array as now there are three elements .. the program would divide into two and one element

and here recursion come into picture

calling the function itself

and then the program would again try to divide the array which has two elements now in to two arrays of one and one

and as i know i don;t have to sort the single element because it is already sorted i will just return it .. so i rote the base case as you can see where i wrote p==n

return this value now the actual part is to combine two sorted array

and here the combining procedure/function is called

question : What is this left [i]=10000 for?

answer : actually i copied the left array in left[] and right one in right[]

and then while comparing it may be the case that all elements of first array will get copied first and then the i index will be one more than the actual one.

so i used a larger number(any large random number you can use but it should be greater than the elements present in both array ) so that while comparing it...that element won't be copied otherwise there will be some garbage value