Sort_int

#define SORT_LENGTH 7

void swap(int *arr,int p, int q){
    int t = arr[p];
    arr[p] = arr[q];
    arr[q] = t;
}

int Partition(int *arr,int begin,int end){
	int m = begin + (end - begin) / 2;
	if (arr[begin] > arr[end]) swap(arr, begin, end);
	if (arr[m] > arr[end]) swap(arr, m, end);
	if (arr[begin] > arr[m]) swap(arr, begin, m);
	int pivotkey = arr[begin];

	while (begin<end){
		while (begin<end&&arr[end] >= pivotkey)end--;
		arr[begin] = arr[end];
		while (begin<end&&arr[begin] <= pivotkey)begin++;
		arr[end] = arr[begin];
	}
	arr[begin] = pivotkey;
	return begin;
}

void InsertSort(int *arr,int begin,int end){
    int i,j;
    int min;
    int len = end-begin+1;
    for(i=1;i<len;i++){
        if(arr[i]<arr[i-1]){
            min = arr[i];
            for(j=i-1;arr[j]>min;j--){
                arr[j+1] = arr[j];
            }
            arr[j+1]=min;
        }
    }
}

void QSort(int *arr,int begin,int end){
    int pivot;
    while(begin<end){
        pivot = Partition(arr,begin,end);
        QSort(arr,begin,pivot);
        begin = pivot + 1;
    }
}

void Sort(int *arr,int begin,int end){
    if((end-begin)>SORT_LENGTH)
        QSort(arr,begin,end);
    else 
        InsertSort(arr,begin,end);
}