#include <algorithm>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <time.h>
#define max_size 100
#define mod 10
using namespace std;
void MergeSort(int *num,int first,int last);
void Merge(int *num,int low,int mid,int high);
void Merge(int *num,int low,int mid,int high){
int i,j,k;
int right_low = mid+1;
int *tmp = (int *)malloc((high-low+1)*sizeof(int));
for (k = 0; low <= mid && right_low <= high ; k++){
if(num[low] <= num[right_low]) tmp[k] = num[low++];
else tmp[k] = num[right_low++];
}
if(low <= mid){
for ( i = low; i <= mid; ++i){
tmp[k++] = num[i];
}
}
if(right_low <= high){
for ( j = right_low; j <= high; ++j){
tmp[k++] = num[j];
}
}
for (int i = 0; i < high-low+1; ++i)
{
num[low+i] = tmp[i];
}
free(tmp);
return;
}
void MergeSort(int *num,unsigned int first,unsigned int last){
int mid = 0;
if(first < last){
mid = (first + last)/2;
MergeSort(num,first,mid);
MergeSort(num,mid+1,last);
Merge(num,first,mid,last);
}
return;
}
int main(){
int num[max_size];
int size;
while(scanf("%d",&size)==1 && size>0){
for (int i = 0; i < size; ++i)
{
cin>>num[i];
}
MergeSort(num,0,size-1);
cout<<num[0];
for (int i = 0; i < size; ++i){
cout<<num[i]<<" ";
cout<<endl;
}
}
return 0;
}
网友评论