// https://www.bilibili.com/video/av9982752/?spm_id_from=333.788.videocard.1

#include <stdio.h>

void merge(int arr[], int L, int M, int R) {
  int LEFT_SIZE = M-L;
  int RIGHT_SIZE = R-M+1;
  int left[LEFT_SIZE];
  int right[RIGHT_SIZE];
  int i,j,k;
  // 下標從L開始
  for(i=L;i<M;i++)
  {
    left[i-L] = arr[i];
  }
  // 下標從M開始
  for(i=M;i<R;i++)
  {
    right[i-M] = arr[i];
  }
  // 重新賦值
  i=0; j=0; k=L;
  // 取小的加一
  while(i<LEFT_SIZE && j<RIGHT_SIZE)
  {
    if(left[i] < right[j]) 
    {
      arr[k] = left[i];
      i++;
      k++;
    } 
    if(right[j] < left[i])
    {
      arr[k] = right[j];
      j++;
      k++;
    }
  }
  // 處理剩下的陣列
  while(i<LEFT_SIZE)
  {
    arr[k] = left[i];
    i++;
    k++;
  }

  // 當原陣列是4個的時候會修改到R的值,造成無窮迴圈
  // 請見下方的測試資料
  while(j<RIGHT_SIZE)
  {
    arr[k] = right[j];
    j++;
    k++;
  }
}

void mergeSort(int arr[], int L, int R)
{
  // 一個以上的元素才會呼叫到遞迴的方法,剩下一個元素不處理
  if(L<R) { 
    return ;
  } else {
    int M = (L+R) / 2;
    // printf("L=%d R=%d M=%d \n",L ,R , M);
    mergeSort(arr, L, M);
    mergeSort(arr, M+1, R);
    merge(arr, L, M+1 ,R);
  }
}

int main() {
  int L = 0;
  int M = 3;
  int R1 = 6;
  int arr[] = {3,9,20,8,21,22};
  // 出現無窮迴圈的情況
  // int M = 2;
  // int R1 = 4;
  // int arr[] = {3,9,8,20};

  // 已經排序好的陣列
  // merge(arr, L, M, R1);
  mergeSort(arr, L, R1);

  int i=0;
  // printf("second arr value %d R1=%d",arr[1], R1);
  for(i=0; i<R1; i++) {
    printf("i=%d, R=%d,arr[i]=%d\n",i,R1, arr[i]);
  }
}