//时间复杂度为O(nlogn), 以2为底

//空间复杂度为O(n)


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#include <assert.h>

#define ARRAY_SIZE 10

void merge(int sortArray[], int st, int md, int end)
{//st and md are the start points of two subarrays respectively

  int i, j, *temp, ptemp;
  i = st;
  j = md;
  ptemp = 0;
  temp = (int*)malloc(sizeof(int)*(end-st+1));
  while(i<md && j<end+1)
  {
    if(sortArray[i]<=sortArray[j])
    {
      *(temp+ptemp) = sortArray[i];
      i++;
    }
    else
    {
      *(temp+ptemp) = sortArray[j];
      j++;
    }
    
    ptemp++;
  }
  if (i>=md)
    for(;ptemp<end-st+1;ptemp++,j++)
      *(temp+ptemp) = sortArray[j];
  else
    for(;ptemp<end-st+1;ptemp++,i++)
      *(temp+ptemp) = sortArray[i];
  memcpy(sortArray+st, temp, ptemp*sizeof(int));
  free(temp);
}

void mergeSort(int sortArray[], int st, int end)
{
  if(end>st)
  {
    mergeSort(sortArray, st, (st+end)/2);
    mergeSort(sortArray, (st+end)/2+1, end);
    merge(sortArray, st, (st+end)/2+1, end);
  }
  
}



int main()
{
  int sortArray[ARRAY_SIZE]={30, 29, 45, 33, 21, 3, 108, 75, 99, 66};
  int i;
  mergeSort(sortArray, 0, 9);
  for(i=0;i<10;i++)
    printf("%d ", sortArray[i]);
  printf("\n");
}