void Merge(int arr[], int aux[], int low, int mid, int high) {
  int k = low, i = low, j = mid + 1;

  while (i <= mid && j <= high) {
    if (arr[i] <= arr[j]) {
      aux[k++] = arr[i++];
    } else {
      aux[k++] = arr[j++];
    }
  }

  while (i <= mid) {
    aux[k++] = arr[i++];
  }

  for (int i = low; i <= high; i++) {
    arr[i] = aux[i];
  }
}
void mergesort(int arr[], int aux[], int low, int high) {

  if (high <= low) {
    return;
  }

  int mid = (low + ((high - low) >> 1));

  mergesort(arr, aux, low, mid);
  mergesort(arr, aux, mid + 1, high);

  Merge(arr, aux, low, mid, high);
}