插入排序（Insert Sort）、归并排序（Merge Sort）和快速排序（Quick Sort）

	//开始对两个数组进行归并 
	i = 0; j = 0;
	for (int k = p; k <= r; k++) {
		if(i == n1){//如果左边数组已经全放进去 
			while(j < n2)	A[k++] = R[j++];
		} else if ( j == n2){//如果右边数组已经全放进去 
			while(i < n1)	A[k++] = L[i++];
		} else{//比较两个数组，把小的数放进A数组，指针后移 
			if (L[i] <= R[j]) {
				A[k] = L[i];
				i++;
			}
			else {
				A[k] = R[j];
				j++;
			}
		}
		
	}
}

void MergeSortUp(int A[], int p,int r)
{
	if (p < r) {
		int q = (p + r) / 2;
		MergeSortUp(A, p, q);
		MergeSortUp(A, q + 1, r);
		Merge(A, p, q, r);
	}
}

void QuickSortUp(int A[], int p, int r)
{
	if (p < r) {
		int q = partition(A, p, r);
		QuickSortUp(A, p, q - 1);
		QuickSortUp(A, q + 1, r);
	}
}

/*Generating test data set*/
void tstdata(int n)
{
	FILE *fp;
	if((fp = fopen("tstdata.txt","w+"))== NULL)
		printf("cant open the file.\n");
	else{
		srand(time(NULL));
		for (int i = 1; i <= n; i++) {
			if(i!=n) fprintf(fp,"%d ",rand());
	      else fprintf(fp,"%d\n",rand());
		}
		fclose(fp);
	}
	
}

/*output function*/
int output(char *filename,int A[])
{
    FILE * fp;
    if((fp = fopen(filename,"w+"))==NULL){
      printf("cant open the file.\n");
    }
    else{
	   for(int i=0;i<size;i++){
		   if(i!=size-1) fprintf(fp,"%d ",A[i]);
		   else fprintf(fp,"%d\n",A[i]);
	   }
	   fclose(fp);
	 }
    
    return 0;
}

main()
{
	int i=0;
	
	/*generating test data*/
	/*tstdata(size);
	printf("Data set has been created.\n");*/
	
	
	/*get the test data*/
	FILE *fp;
	if((fp = fopen("tstdata.txt","r"))==NULL){
		printf("cant open the file.\n");
    }
	while(fscanf(fp, "%d", &A[i]) != EOF) 
        i++;
   fclose(fp);
	 for(i=0;i<size;i++){
	 	printf("%d ",A[i]);
	 } 
	 printf("\n");
	 printf("Array has been created.\n");
	   
	    
	/*copy the test data set*/
	int A1[size],A2[size],A3[size];
	for(int i=0;i<size;i++){
		A1[i]=A[i];
		A2[i]=A[i];
		A3[i]=A[i];
	}
	

    /*Insert Sorting*/
	printf("Insert Sorting...\n");
	
	start = clock();
	InsertSortUp(A1,size);
	finish = clock();
	
	output("InsertSortUp.txt",A1);
	runtime_insert = (double)(finish - start)/CLOCKS_PER_SEC;
	printf("Insert Sort has been finished.\nTime Cost:%lf\n",runtime_insert);
	
	
    /*Merge Sorting*/
	printf("Merge Sorting...\n");
	
	start = clock();
	MergeSortUp(A2,0,size-1);
	finish = clock();
	
	output("MergeSortUp.txt",A2);
	runtime_merge = (double)(finish-start)/CLOCKS_PER_SEC;
	printf("Merge Sort has been finished.\nTime Cost:%lf\n",runtime_merge);

    /*Quick Sorting*/
	printf("Quick Sorting...\n");
	
	start = clock();
	QuickSortUp(A3,0,size-1);
	finish = clock();
	
	output("QuickSortUp.txt",A3);
	runtime_quick = (double)(finish-start)/CLOCKS_PER_SEC;
	printf("Quick Sort has been finished.\nTime Cost:%lf\n",runtime_quick);
	

}

if(i == n1){//如果左边数组已经全放进去 
			while(j < n2)	A[k++] = R[j++];
		} else if ( j == n2){//如果右边数组已经全放进去 
			while(i < n1)	A[k++] = L[i++];
		}

//median-of-three pivot rule
private static int choosePivotMedianOfThree(int[] a, int l, int r) {	
	int mid = 0;
	if ((r-l+1) % 2 == 0) {
		mid = l + (r-l+1)/2 - 1;
	} else {
		mid = l + (r-l+1)/2;
	}

	//只需要找出中位数即可，不需要交换
    //有的版本也可以进行交换
	if (((a[l]-a[mid]) * (a[l]-a[r])) <= 0) {
		return l;
	} else if (((a[mid]-a[l]) * (a[mid]-a[r])) <= 0) 	{
		return mid;
	} else {
		return r;
	}
}
--------------------- 
/*作者：xinyuexy 
 *来源：CSDN 
 *原文：https://blog.csdn.net/qq_31903733/article/details/82945605 
 *版权声明：本文为博主原创文章，转载请附上博文链接！*/