排序 （C++代码）（非STL的SORT）

解题思路:
这是一种分治思维，现将所排序选择的数字定位，再将左右两边的数用递归的方式再度进行这样的排序，此排序的时间复杂度为O（NlogN）
注意事项:

参考代码:

（请不要直接抄袭）

#include<bits/stdc++.h>
#define maxn 10005
using namespace std;
int a[maxn],f[maxn];
void merge(int a[],int l,int m,int r) {
	int i=l,j=m;
	int p=l;
	while(i<m&&j<r) {
		if(a[i]<a[j]) {
			f[p++]=a[i++];
		} else {
			f[p++]=a[j++];
		}
	}
	while(i<m) {
		f[p++]=a[i++];
	}
	while(j<r) {
		f[p++]=a[j++];
	}
	for(int i=l; i<r; i++) {
		a[i]=f[i];
	}
}

void mysort(int a[],int l,int r) {
	if(l+1<r) {
		int m=(l+r)/2;
		mysort(a,l,m);
		mysort(a,m,r);
		merge(a,l,m,r);
	}
}

int main() {
	int n;
	while(scanf("%d",&n)!=EOF) {
		for(int i=0; i<n; i++)
			cin>>a[i];
			
		srand(time(NULL));	//乱搞数据
		for(int i=0; i<n/2; i++) {
			swap(a[i],a[rand()%n]);
		}
		
		mysort(a,0,n);
		for(int i=0; i<n; i++) {
			printf("%d ",a[i]);
		}
		cout<<endl;
	}
	return 0;
}

想到了一个毒瘤数据：

如果本身排序的数组就是逆序排序好了的，那么我们进行这样的排序将采用最坏情况，即时间复杂度高达O(n^2)的情况，这显然是容易在竞赛中GG的，所以为了避免毒瘤数据的出现。

我才用了随机数种子的方法把数据乱搞一通（打乱数组）这样就用了一种非常虚伪的方式实现了本排序算法时间复杂度趋向于O(n log n)的情况。