struct Cell
{
  int data;
  int occur;
};
void mergeSort(struct Cell* space, int pos_start, int pos_end)
{
  if(pos_start < pos_end)
    {
      int pos_mid = (pos_start + pos_end) / 2;
      mergeSort(space, pos_start, pos_mid);
      mergeSort(space, pos_mid + 1, pos_end);
      merge(space, pos_start, pos_mid, pos_end);
    }
  return;
}

void merge(struct Cell* space, int pos_start, int pos_div, int pos_end)
{
  int length_left = pos_div - pos_start + 1;
  int length_right = pos_end - pos_div;
  struct Cell* space_left = (struct Cell*) malloc(length_left * sizeof(struct Cell));
  struct Cell* space_right = (struct Cell*) malloc(length_right * sizeof(struct Cell));
  int i, j, k;

  //Reallocate two arrays
  for(i = 0; i < length_left; i++)
    {
      space_left[i].data = space[pos_start + i].data;
      space_left[i].occur = space[pos_start + i].occur;
    }

  for(j = 0; j < length_right; j++)
    {
      space_right[j].data = space[pos_div + j + 1].data;
      space_right[j].occur = space[pos_div + j + 1].occur;
    }

  i = j = 0;

  for(k = pos_start; k <= pos_end; k++)
    {
      if(j >= length_right)
	{
	  space[k].data = space_left[i].data;
	  space[k].occur = space_left[i].occur;
	  i++;
	}      
      else if(i >= length_left)
	{
	  space[k].data = space_right[j].data;
	  space[k].occur = space_right[j].occur;
	  j++;
	}
      else if(space_left[i].data <= space_right[j].data)
	{
	  space[k].data = space_left[i].data;
	  space[k].occur = space_left[i].occur;
	  i++;
	}
      else
	{
	  space[k].data = space_right[j].data;
	  space[k].occur = space_right[j].occur;
	  j++;
	}
    }

  free(space_left);
  free(space_right);
  
  return;
}