/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 void merge(int *a,int l,int r,int *z){
     if(l>=r)return;
     int mid=l+(r-l)/2;
     merge(a,l,mid,z);
     merge(a,mid+1,r,z);
     int i=l,j=mid+1,k=0;
     while(i<=mid&&j<=r){
         if(a[j]>a[i]){
             z[k++]=a[i++];
         }
         else{
             z[k++]=a[j++];
         }
     }
     while(i<=mid){
         z[k++]=a[i++];
     }
     while(j<=r){
         z[k++]=a[j++];
     }
     for(int o=l,p=0;o<=r;o++,p++){
         a[o]=z[p];
     }
 }
#include <stdlib.h>
 void quicksort(int *a,int l,int r){
     if(l>=r)return;
     int x=rand()%(r-l)+l;
     int tmp=a[x];
     a[x]=a[l],a[l]=tmp;
     int i=l,j=r;
     while(i<j){
         while(a[j]>=tmp&&i<j){
             j--;
         }
         if(i<j){
             a[i++]=a[j];
         }
         while(a[i]<tmp&&i<j){
             i++;
         }
         if(i<j){
             a[j--]=a[i];
         }
     }
     a[j]=tmp;
     quicksort(a,l,i-1);
     quicksort(a,i+1,r);
 }
int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize=numsSize;
    //int *z=(int *)malloc(sizeof(int)*numsSize);
    //merge(nums,0,numsSize-1,z);
    quicksort(nums,0,numsSize-1);
    return nums;
}