You know sorting is very important. And this easy problem is:
Given you an array with N non-negative integers which are smaller than 10,000,000, you have to sort this array. Sorting means that integer with smaller value presents first.
The first line of the input is a positive integer T. T is the number of the test cases followed.
The first line of each test case is a positive integer N (1<= N<= 1000) which represents the number of integers in the array. After that, N lines followed. The i-th line is the i-th integer in the array.
2 3 1 2 3 1 1
1 2 3 1
#include<cstdio>
#define MAX 1001
int a[MAX], aux[MAX];
//2路归并排序
void merge_sort(int lo, int hi)
{
if (lo < hi)
{
int mid = lo + (hi - lo)/2;
merge_sort(lo, mid); //递归
merge_sort(mid+1, hi);
for (int i = lo; i <= hi; ++i) //赋初值
aux[i] = a[i];
int l = lo, r = mid+1;
for (int i = lo; i <= hi; i++)
{
if (l > mid) a[i] = aux[r++]; //第一路已经处理完
else if (r > hi) a[i] = aux[l++]; //第二路已经处理完
else if (aux[r] < aux[l]) a[i] = aux[r++]; //二路比较
else a[i] = aux[l++];
}
}
}
int main()
{
int t, n;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]);
merge_sort(0, n-1);
for (int i = 0; i < n; ++i)
printf("%d\n", a[i]);
}
return 0;
}
原文：http://www.cnblogs.com/KennyRom/p/6251031.html