병합 정렬

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

/*
병합정렬
1. 나눌수 있는 최소한의 배열로 쪼갠다
2. 합친다.
*/
void merge(int left, int mid, int right, int arr[])
{
  // 0, 1, 3
  int n1 = mid - left + 1;
  int n2 = right - mid;
  int left_arr[n1];
  int right_arr[n2];

  // 배열 초기화

  for (int i = 0; i < n1; i++)
  {
    // i : 0 ~ 1까지
    // left + i : 0 ~ 1 까지
    left_arr[i] = arr[left + i];
  }
  for (int i = 0; i < n2; i++)
  {
    // i : 0~ 1 까지
    // mid + 1 + i : 2 ~ 3 까지
    right_arr[i] = arr[mid + 1 + i];
  }
  // 갱신할 배열 인덱스 idx
  // 좌측 배열 인덱스 p
  // 우측 배열 인덱스 q
  int idx=left, p =0, q = 0;
  while (p < n1 && q < n2)
  {
    if (left_arr[p] <= right_arr[q])
    {
      arr[idx++] = left_arr[p++];
    }
    else
    {
      arr[idx++] = right_arr[q++];
    }
  }

  while (p < n1)
  {
    arr[idx++] = left_arr[p++];
  }
  while(q < n2)
  {
    arr[idx++] = right_arr[q++];
  }
  
}







void merge_sort(int left, int right, int arr[])
{

  
  if (left < right)
  {
    int mid = (left + right) / 2;
    merge_sort(left, mid, arr); // 0, 3 -> 0, 1 -> 
    merge_sort(mid + 1, right, arr); // 4, 7 -> 5, 7 -> 6, 7
    merge(left, mid, right, arr);

    for (int i =0; i <8; i++)
    {
      printf("%d ", arr[i]);
    }
    printf("\n");
  }
  return;
  

}


int main(void)
{
  int arr[8] = {3, 21, 5, 9, 2, 64, 17, 24}; 

  merge_sort(0, 7, arr);


  return 0;
}