50213. Merge Sort
難度：3/5
相信大家被DSA摧殘過都很會手刻Merge Sort。temp_arr不要每次進到merge的時候重新宣告，不然會TLE。
Second Try: 3/5 Used Time: 15:551
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <ctype.h>
void print_arr(int arr[], int l, int r){
for(int i = l; i <= r; i++){
printf("%d%c", arr[i], (i == r) ? '\n' : ' ');
}
}
static inline int get_mid(int a, int b){
if((b - a) % 2 == 1){
return (a + b) / 2 + 1;
}
else{
return (a + b) / 2;
}
}
void merge(int arr[], int l, int r, int temp_arr[]){
int m = get_mid(l, r);
int ptr_a = l, ptr_b = m, temp_ptr = l;
while(ptr_a < m && ptr_b <= r){
if(arr[ptr_a] < arr[ptr_b]){
temp_arr[temp_ptr++] = arr[ptr_a++];
}
else{
temp_arr[temp_ptr++] = arr[ptr_b++];
}
}
while(ptr_a < m) temp_arr[temp_ptr++] = arr[ptr_a++];
while(ptr_b <= r) temp_arr[temp_ptr++] = arr[ptr_b++];
for(int i = l; i <= r; i++) arr[i] = temp_arr[i];
}
void merge_sort(int arr[], int l, int r, int temp_arr[]){
print_arr(arr, l, r);
if(l == r) return;
int m = get_mid(l, r);
merge_sort(arr, l, m - 1, temp_arr);
merge_sort(arr, m, r, temp_arr);
merge(arr, l, r, temp_arr);
print_arr(arr, l, r);
}
int main(){
int n = 0, arr[100005] = {0}, temp_arr[100005] = {0};
while(scanf("%d", &arr[n]) != EOF) n++;
merge_sort(arr, 0, n - 1, temp_arr);
}