#include <stdio.h>
#include <stdlib.h>

void Merge(int arr[], int left, int mid, int right)
{
    int leftStart = left;
    int leftEnd = mid;
    int rightStart = mid + 1;
    int rightEnd = right;
    int index = 0;
 
    // 합병한 결과를 담은 배열 동적 할당
    int* sortedArr = (int*)malloc(sizeof(int)*(right + 1));
    int sortedArrIndex = left;

    while ((leftStart <= leftEnd) && (rightStart <= rightEnd)) {
        if (arr[leftStart] > arr[rightStart]) {
            sortedArr[sortedArrIndex] = arr[rightStart++];
        }
        else { 
            sortedArr[sortedArrIndex] = arr[leftStart++];
        }
        sortedArrIndex++;
    }
    
    // 배열의 앞부분이 모두 정렬된 배열에 옮겨졌다면
    if (leftStart > leftEnd) {
        // 배열의 뒷부분에 남은 데이터를 그대로 옮긴다.
        for (index = rightStart; index <= rightEnd; index++) {
            sortedArr[sortedArrIndex++] = arr[index];
        }
    }

    // 배열의 뒷부분이 모두 정렬된 배열에 옮겨졌다면
    else {
        // 배열의 앞부분에 남은 데이터를 그대로 옮긴다.
        for (index = leftStart; index <= leftEnd; index++) {
            sortedArr[sortedArrIndex++] = arr[index];
        }
    }

    for (index = left; index <= right; index++)
        arr[index] = sortedArr[index];

    free(sortedArr);
}

void MergeSort(int arr[], int left, int right)
{
    int mid;

    // left가 더 작은 경우는 더 나눌 수 있는 경우
    if (left < right) {
        // 중간 지점 계산
        mid = (left + right) / 2;
        
        // left부터 mid까지의 데이터 정렬
        MergeSort(arr, left, mid);

        // mid+1부터 right까지의 데이터 정렬
        MergeSort(arr, mid + 1, right);

        // 정렬된 두 배열을 합병하기
        Merge(arr, left, mid, right);
    }
}

int main(void)
{
    int arr[] = { 6, 3, 9, 1, 2, 7 };
    int index = 0;
    int arrSize = (sizeof(arr) / sizeof(int));

    MergeSort(arr, 0, arrSize-1);

    for (index = 0; index < arrSize; index++)
        printf("%d ", arr[index]);
 
    return 0;
}