Merge Sort in C language

Merge Sort

This is a one kind of sorting technique. The complexity of this sorting technique is,
Worst-case performance : O(n log n)
Best-case performance : O(n log n)
Average-case performance : O(n log n)
For more details click here

Code

/******Merge Sort*****/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
//Function declaration
int* merge(int*,int,int,int);
//Function definition for merge sort
int* merge_sort(int *arr,int left,int right){
 int mid;
 if(right>left){
  mid=(left+right)/2;
  merge_sort(arr, left, mid);
  merge_sort(arr,mid+1,right);
  merge(arr,left,mid+1,right);
 }
 return arr;
}
//Function definition for merge two array
int* merge(int *arr,int left,int mid,int right){
 int *temp,i,x,no_of_element;
 no_of_element=right-left+1;
 x=left;
 temp=(int*)malloc(no_of_element*sizeof(int)); 
 while((left<=mid-1)&&(mid<=right)) {
  if(arr[left]<=arr[mid])  {
   temp[x++]=arr[left];
   left++;
  }
  else  {
   temp[x++]=arr[mid];
   mid++;
  }
 }
 while(left<=mid-1)
  temp[x++]=arr[left++];
 while(mid<=right)
  temp[x++]=arr[mid++];
 for(i=0;i<no_of_element;i++) {
  arr[right]=temp[right];
  right--;
 }
 return arr;
}
//Main function start
int main()
{
 int *arr,n,i;
 while(1){
  //taking the number of element
  printf("\nEnter the number of element you want to store:");
  scanf("%d",&n);
  if(n<=0){
   printf("\nAn array size must be a positive integer.");
   continue;
  }
  else
   break;
 }
 //Creating array dynamically
 arr=(int*)malloc(n*sizeof(int));
 if(!arr){
  printf("\nNot enough memory.");
  exit(0);
 }
 //Taking the element from user
 printf("\nEnter the element(s) in the array:");
 for(i=0;i<n;i++){
  printf("\nElement[%d]:",i+1);
  scanf("%d",&arr[i]);
 }
 //Print the element before sorting
 printf("\nThe element(s) before sorting:");
 for(i=0;i<n;i++)
  printf(" %d",arr[i]);
 printf("\nThe element(s) after sorting:");
 //Call the function
 arr=merge_sort(arr,0,n-1);
 //Print the sorted array
 for(i=0;i<n;i++)
  printf(" %d",arr[i]);
 return 0;
}

Output

Enter the number of element you want to store:5

Enter the element(s) in the array:
Element[1]:1

Element[2]:8

Element[3]:3

Element[4]:2

Element[5]:5

The element(s) before sorting: 1 8 3 2 5
The element(s) after sorting: 1 2 3 5 8