// Copyright 2023 Jeisson Hidalgo jeisson.hidalgo@ucr.ac.cr CC-BY-4
// Adapted from
// cw.fel.cvut.cz/old/_media/courses/b4m35pag/lab6_slides_advanced_openmp.pdf
#include <algorithm>
#include <vector>

template <typename Type>
void bubble_sort(std::vector<Type>& values, const long start = 0
    , long finish = -1) {
  finish = finish < 0 ? values.size() : finish;
  for (size_t i = start; i < finish - start - 1; ++i) {
    for (size_t j = start; j < finish - i - 1; ++j) { 
      if (values[j] > values[j + 1]) {
        std::swap(values[j], values[j + 1]);
      }
    }
  }
}

// TODO(you): parallelize merge sort
template <typename Type>
void mergesort(std::vector<Type>& values, const ptrdiff_t left,
    const ptrdiff_t right) {
  const ptrdiff_t count = right - left;
  if (count > 0) {
    if (count >= 32) {
      const size_t mid = (left + right) / 2;

      #pragma omp taskgroup
      {
        #pragma omp task untied shared(values) if(count >= (1<<14))
        mergesort(values, left, mid);
        #pragma omp task untied shared(values) if(count >= (1<<14))
        mergesort(values, mid + 1, right);
        #pragma omp taskyield
      }

      // TODO(jhc): move to merge() subroutine
      std::vector<Type> temp;
      std::merge(values.begin() + left, values.begin() + mid + 1,
          values.begin() + mid + 1, values.begin() + right + 1,
          std::back_inserter(temp));
      std::copy(temp.begin(), temp.end(), values.begin() + left);
    } else {
      // TODO(jhc): replace by O(n^2) sort such as bubblesort
      std::sort(values.begin() + left, values.begin() + right + 1);
      // bubble_sort(values, left, right + 1);
    }
  }
}

template <typename Type>
void mergesort(std::vector<Type>& values) {
  #pragma omp parallel
  #pragma omp single
  mergesort(values, 0, values.size() - 1);
}