43 lines
859 B
C
43 lines
859 B
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
void merge(int* arr, int l, int r){
|
|
int mid = (l + r) / 2;
|
|
int tmp[114514];
|
|
int p = 0;
|
|
int i = l, j = mid + 1;
|
|
while( i <= mid && j <= r){
|
|
if(arr[i] <= arr[j]) tmp[p++] = arr[i++];
|
|
else tmp[p++] = arr[j++];
|
|
}
|
|
while(i <= mid) tmp[p++] = arr[i++];
|
|
while(j <= r) tmp[p++] = arr[j++];
|
|
|
|
for(size_t x = l; x <= r; x++){
|
|
arr[x] = tmp[x - l];
|
|
}
|
|
}
|
|
void mergesort(int* arr, int l, int r){
|
|
if(l >= r) return;
|
|
int mid = (l + r) / 2;
|
|
mergesort(arr, l, mid);
|
|
mergesort(arr, mid + 1, r);
|
|
merge(arr, l, r);
|
|
}
|
|
|
|
int main(){
|
|
int n;
|
|
scanf("%d", &n);
|
|
int* arr = (int*)malloc(n * sizeof(int));
|
|
for(int i = 0; i < n; ++i){
|
|
scanf("%d", &arr[i]);
|
|
}
|
|
mergesort(arr, 0, n - 1);
|
|
for(int i = 0; i < n; ++i){
|
|
printf("%d ", arr[i]);
|
|
}
|
|
printf("\n");
|
|
return 0;
|
|
}
|