Count Inversions in an array

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

int mergeSort(int arr[], int temp[], int left, int right)
{
   int count = 0;
  if (right > left)
  {
int mid = (right + left)/2;
      count = mergeSort(arr, temp, left, mid);
      count += mergeSort(arr, temp, mid+1, right);
      count += merge(arr, temp, left, mid, right);
  }
return count;
}
  
int merge(int arr[], int temp[], int left, int mid, int right)
{
  int i, j, k;
  int count1 = 0;
  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++];
      count1 += (mid - i);
    }
  }
  
  while (i <= mid)
    temp[k++] = arr[i++];
  
  while (j <= right)
    temp[k++] = arr[j++];
  
  for (i=left; i <= right; i++)
    arr[i] = temp[i];
  }

Merge sort using Linked List

struct node
{
    int data;
    struct node* next;
};
  
void MergeSort(struct node** headRef)
{
  struct node* head = *headRef;
  struct node* a;
  struct node* b;
   if ((head == NULL) || (head->next == NULL)){
    return;
  }
  FrontBackSplit(head, &a, &b); 
  MergeSort(&a);
  MergeSort(&b);
  *headRef = SortedMerge(a, b);
}
 
struct node* SortedMerge(struct node* a, struct node* b)
{
  struct node* result = NULL;
 
  if (a == NULL)
     return(b);
  else if (b==NULL)
     return(a);

  if (a->data <= b->data){
     result = a;
     result->next = SortedMerge(a->next, b);
  }
  else {
     result = b;
     result->next = SortedMerge(a, b->next);
  }
  return(result);
}
 
/* Split the nodes of the given list into front and back halves.
     If the length is odd, the extra node should go in the front list. */
void FrontBackSplit(struct node* source, struct node** frontRef, 
                    struct node** backRef){
  struct node* fast;
  struct node* slow;

  if (source==NULL || source->next==NULL) {
    *frontRef = source;
    *backRef = NULL;
  }
  else {
    slow = source;
    fast = source->next;
 
    /* Advance 'fast' two nodes, and advance 'slow' one node */
    while (fast != NULL)
    {
      fast = fast->next;
      if (fast != NULL)
      {
        slow = slow->next;
        fast = fast->next;
      }
    }
 
    /* 'slow' is before the midpoint in the list, so split it in two
      at that point. */
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
  }
}

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