머지 정렬 Merge Sort

동빈나의 머지소트

 

#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;
}