#ifndef SORT_ALGORITHMS_HPP
#define SORT_ALGORITHMS_HPP

#include <cstdint>
#include <utility>

template<typename T>
class row;

template<typename T>
void bubble_sort(row<T>& s) {
	uint32_t n = s.size();
	for (uint32_t i=0;i<n;i++)
		for(uint32_t j=0;j<n-i-1;j++)
			if (s[j] > s[j+1])
				std::swap(s[j],s[j+1]);
}

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]);
	}
}

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;
	}
}

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);
}

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(row<T>& s) {
	if (s.size() > 1) quick_sort_recursive(s,0,s.size()-1);
}

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;
			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