Merge Sort

int *temp = (int *)malloc(sizeof(int)*array_size);  

int mergeSort(int arr[], int temp[], int left, int right)
{
  if (right > left)
  {
int mid = (right + left)/2;
      mergeSort(arr, temp, left, mid);
      mergeSort(arr, temp, mid+1, right);
      merge(arr, temp, left, mid, right);
  }
}
  
int merge(int arr[], int temp[], int left, int mid, int right)
{
  int i, j, k;
  
  i = left;
  j = mid+1; 
  k = left;
  
   while ((i <= mid) && (j <= right))
   {
    if (arr[i] <= arr[j])
    {
      temp[k++] = arr[i++];
    }
    else
    {
      temp[k++] = arr[j++];
    }
  }
  
  while (i <= mid)
    temp[k++] = arr[i++];
  
  while (j <= right)
    temp[k++] = arr[j++];
  
  for (i=left; i <= right; i++)
    arr[i] = temp[i];
  }

Time Complexity: O(nLog(n))