//#pragma once== SAME
#ifndef SORT_ALGORITHMS_HPP
#define SORT_ALGORITHMS_HPP

#include <cstdint>
#include <utility>   // for std::swap

// Forward declaration of container
template<typename T>
class row;


/* =========================
   BUBBLE SORT
   ========================= */
template<typename T>
void bubble_sort(row<T>& s)
{
    uint32_t n = s.size();

    for (uint32_t i = 0; i < n - 1; ++i)
        for (uint32_t j = 0; j < n - i - 1; ++j)
            if (s[j] > s[j + 1])
                std::swap(s[j], s[j + 1]);
}


/* =========================
   SELECTION SORT
   ========================= */
template<typename T>
void selection_sort(row<T>& s)
{
    uint32_t n = s.size();

    for (uint32_t i = 0; i < n - 1; ++i) {
        uint32_t min_idx = i;

        for (uint32_t j = i + 1; j < n; ++j)
            if (s[j] < s[min_idx])
                min_idx = j;

        std::swap(s[i], s[min_idx]);
    }
}


/* =========================
   INSERTION SORT
   ========================= */
template<typename T>
void insertion_sort(row<T>& s)
{
    uint32_t n = s.size();

    for (uint32_t i = 1; i < n; ++i) {
        T key = s[i];
        int32_t j = i - 1;

        while (j >= 0 && s[j] > key) {
            s[j + 1] = s[j];
            --j;
        }

        s[j + 1] = key;
    }
}


/* =========================
   MERGE SORT
   ========================= */

template<typename T>
void merge(row<T>& s, uint32_t left, uint32_t mid, uint32_t right)
{
    uint32_t n1 = mid - left + 1;
    uint32_t n2 = right - mid;

    T* L = new T[n1];
    T* R = new T[n2];

    for (uint32_t i = 0; i < n1; ++i)
        L[i] = s[left + i];

    for (uint32_t j = 0; j < n2; ++j)
        R[j] = s[mid + 1 + j];

    uint32_t i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j])
            s[k++] = L[i++];
        else
            s[k++] = R[j++];
    }

    while (i < n1)
        s[k++] = L[i++];

    while (j < n2)
        s[k++] = R[j++];

    delete[] L;
    delete[] R;
}

template<typename T>
void merge_sort_recursive(row<T>& s, uint32_t left, uint32_t right)
{
    if (left < right) {
        uint32_t mid = left + (right - left) / 2;

        merge_sort_recursive(s, left, mid);
        merge_sort_recursive(s, mid + 1, right);
        merge(s, left, mid, right);
    }
}

template<typename T>
void merge_sort(row<T>& s)
{
    if (s.size() > 1)
        merge_sort_recursive(s, 0, s.size() - 1);
}


/* =========================
   QUICK SORT
   ========================= */

template<typename T>
int partition(row<T>& s, int low, int high)
{
    T pivot = s[high];
    int i = low - 1;

    for (int j = low; j < high; ++j) {
        if (s[j] < pivot) {
            ++i;
            std::swap(s[i], s[j]);
        }
    }

    std::swap(s[i + 1], s[high]);
    return i + 1;
}

template<typename T>
void quick_sort_recursive(row<T>& s, int low, int high)
{
    if (low < high) {
        int pi = partition(s, low, high);

        quick_sort_recursive(s, low, pi - 1);
        quick_sort_recursive(s, pi + 1, high);
    }
}

template<typename T>
void quick_sort(row<T>& s)
{
    if (s.size() > 1)
        quick_sort_recursive(s, 0, s.size() - 1);
}

/* =========================
   ENUMERATION SORT (RANK SORT)
   ========================= */

template<typename T>
void enumeration_sort(row<T>& s)
{
    uint32_t n = s.size();

    if (n <= 1)
        return;

    T* temp = new T[n];

    for (uint32_t i = 0; i < n; ++i) {

        uint32_t rank = 0;

        for (uint32_t j = 0; j < n; ++j) {

            if (s[j] < s[i])
                ++rank;

            // Handle duplicates safely
            if (s[j] == s[i] && j < i)
                ++rank;
        }

        temp[rank] = s[i];
    }

    for (uint32_t i = 0; i < n; ++i)
        s[i] = temp[i];

    delete[] temp;
}
#endif