program explaining merge sort without saving the random number in left and right array

lot of people are finding difficulty in left[i]= 10000 so here's the solution 
well in my previous blog yesterday the approach that i followed was similar to cormen where they initialize the the next  element after filling the let and right sub array as ∞ which means the element should be higher than all the elements present for sorting but that may not be the case .. as you will never know what a person can enter . 
here some people will say that we can enter the largest that is available for that language for example for c it signed 32467 ( for 32 bit compiler ) and it can also vary from system to system so you can  use this approach 
#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 n2 = x;
    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]);

    }


    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]);

    }
    printf("\n");
    p=n1; /*now p contains the starting value as we modified the value in first loop */
    for(i=0,j=0;(i<n2-n1+1)&&(j<n-n2);p++) /* as (n2-n1+1) would be giving the number of elements in left array but here in left array we are starting from 0 that's why we didn't use equal to sign*/
    {
        if((i!=n2-n1+1)&&(left[i]<right[j]))
        {
            A[p]=left[i];
            printf("the element added in A[%d] which is %d \n",n1,A[p]);
            i++;
        }
        else
        {

            A[p]= right[j];
            printf("the element added from right \n",A[p]);
            j++;
        }
    }
    if(i == n2-n1+1 ) /*means all the elements of the left array are copied but there can be elements in right */
    {
        for(;j<n2-n1;j++)
        {
            A[p]=right[j];
            p++;
        }

    }
    else /*means all the elements of the right  array are copied but there can be elements in left */
    {
        for(;i<n2-n1+1;i++)
        {
            A[p]=left[i];
            p++;
        }
    }
}

when i am combing the arrays the loop will come out if only the i or j  index have reached boundry conditions and now in if else condition i am checking which index has achieved boundary conditions as if it j then i will simply copy all the elements of left array in A that is the final array or if it was i then i am copying all the remaining elements from left array . 

Here i tried to keep the previous program as it is ..with minimal changes ... so that you can understand the idea .. well other approaches are also possible .. 

as once a great mathematician said " there are infinitely many solutions possible for a single  problem " 

so try to program it and find newer approaches by yourself  

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