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

//check whether an array of integers is sorted
int checkSorted (int array[], int size)
{
  int i, unsorted = 0;
  for (i = 1; i < size; i++)
  {
    if (array[i-1] > array[i])
    {
      printf ("The array is not in sorted order at position %d\n", i - 1);
      if (!unsorted)
        unsorted++;
    }
  }
  if (!unsorted)
    printf ("The array is sorted !\n");
  return 1;
}

void print_array(int a[], int size)
{
  int i = 0;
  for(i=0;i<size;i++)
    printf("%d ",a[i]);
  printf("\n");
}

//merge sort a[l..r]
void msort(int a[], int l, int r, int b[])
{
  if(r > l)
  {
    int i, j, k, m;
    m=(r+l)/2;
    msort(a,l,m,b);
    msort(a,m+1,r,b);
    //copy left half to temporary array
    for(i=m+1; i>l; i--) b[i-1] = a[i-1];
    //copy right half to temporary array
    for(j=m; j<r; j++) b[r+m-j] = a[j+1];
    //merge both halves into a
    for(k=l; k<=r; k++)
      a[k] = (b[i] < b[j]) ? b[i++] : b[j--];
    }
}

int mergesort(int a[], int size)
{
  //allocate a temporary array used for the merge process
  int* tmp = (int*)malloc(size * sizeof(int));
  if(tmp)
  {
    msort(a,0,size-1,tmp);
    free(tmp);
    return 1;
  }
  else
    return 0;
}



//quicksort a[l..r] with last element as pivot
void myqsort(int a[], int l, int r)
{
  if(r > l)
  {
    int i = l-1, j = r, tmp;
    for(;;)
    {
      while(a[++i] < a[r]);
      while(a[--j] > a[r] && j > i);
      if(i >= j)
        break;
      tmp = a[i]; a[i] =a [j]; a[j] = tmp;
    }
    tmp = a[i]; a[i] = a[r]; a[r] = tmp;
    myqsort(a,l,i-1);
    myqsort(a,i+1,r);
  }
}

void quicksort(int a[], int size)
{
  myqsort(a,0,size-1);
}



int main()
{
  //int arr[] = {1,2,4,6,8,5,3,7,9};
  int arr[] = {1,2,3,4,6,7,8,9,5};
  print_array(arr,sizeof(arr)/sizeof(int));
  checkSorted(arr,sizeof(arr)/sizeof(int));
  quicksort(arr,sizeof(arr)/sizeof(int));
  //mergesort(arr,sizeof(arr)/sizeof(int));
  printf("\n\n");
  print_array(arr,sizeof(arr)/sizeof(int));
  checkSorted(arr,sizeof(arr)/sizeof(int));

  return 0;
}