Merge Sort Code : Shubham Mishra

#include<stdio.h>
#include<conio.h>

void merge_sorting_function( int[], int, int);
void merge_with_sorting_function( int[], int, int, int);

void main(){
 
 //Here I have considered my own array u can replace it with actual code for accepting 
 // it from user
 int array = [34, 5, 9, 14, 64, 8];
 int n = sizeof(array);
 int i;
 
 //Call merge_sorting_function
 merge_sorting_function(array, 0, n-1);
 
 //Now print the sorted array
 for(i=0; i<n; i++)
  printf("%d", array[i]);
 
 getch();
}

void merge_sorting_function(int array[], int i, int j){
 int k;
 if (i<j)  //Condition checked for further division of array into subarray or not
 {
  k = (i+j) / 2;    // Find out the centre point for division
  merge_sorting_function( array, i, k);       //Apply merge sort steps for left sub array

  merge_sorting_function( array, k+1, j);  //Apply merge sort steps for right sub array

  merge_with_sorting_function( array, i, k, j);  //This is imp call for actual merging subarrays

 }
}

void merge_with_sorting_function( int array[], int l, int m, int u){
 //The l,m,u are nothing but the indexes used to get the subarrays
 //The left subarray is from l to m, the right sub array is from m+1 to u
 int temp[100]; //This temp array is used for merging
 int i,j,k;
 
 i = l;
 j = m+1;
 k = 0;
 while( i <= m && j <= u){  //merging two subarrays
  if( array[i] < array[j]){  //Checking which entity is bigger
    temp[k] = array[i];
   i++;
   k++;
  }
  else{
   temp[k] = array[j];
   j++;
   k++;
  }
 }
 
 //Below two while loops are used to copy remaning part of subarrays into temp
 /*Suppos two subarrays are of size 3 and 5, Once all the element of any one subarray
 is transfered to temp array then remaining elements of another array is copied to
   the temp array
 */
 
 while( i <= m){
  temp[k] = array[i];
  i++;
  k++;
 }
 
 while( j <= u){
  temp[k] = array[j];
  j++;
  k++;
 }
 
 //Now copy the sorted temp array back into the original array
 for( i = l, j = 0; i <= u; i++, j++)
  array[i] = temp[j];
}