동빈나의 머지소트
#include <bits/stdc++.h>
using namespace std;
int number = 8;
int sorted[8]; //정렬 배열은 받드시 전역 배열
void merge(int a[], int m, int middle, int n){ //m : 시작점, middle : 중간점, n : 끝점
int i = m;
int j = middle+1;
int k = m;
//작은 순서대로 배열에 삽입
while(i <= middle && j <= n){
if(a[i] <= a[j]){
sorted[k] = a[i];
i++;
}
else{
sorted[k] = a[j];
j++;
}
k++;
}
if(i > middle){
for(int t = j; t<=n; t++){
sorted[k] = a[t];
k++;
}
}
else{
for(int t=i; t<=middle; t++){
sorted[k] = a[t];
k++;
}
}
//sorted 에서 a배열로 옮겨준다
for(int t=m; t<=n; t++){
a[t] = sorted[t];
}
}
void mergesort(int a[], int m, int n){
//크기가 1보다 큰 경우
if(m < n){
int middle = (m+n)/2;
mergesort(a, m, middle);
mergesort(a, middle+1, n);
merge(a,m, middle, n);
}
}
int main()
{
int array[8] = {7,6,5,8,3,5,9,1};
mergesort(array, 0, number-1);
for(int t=0; t<number; t++){
printf("%d ", array[t]);
}
return 0;
}