Timsort

// ConsoleApplication3.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"

using std::cin;
using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::stack;
using std::pair;
using std::string;

typedef int VectorType;
typedef unsigned int ui32;

//int count = 0;
//unsigned int  uk = 0, time1 = 0, time2 = 0, time3 = 0, timer;

template <typename T>
struct UserCompare {
	bool operator () (const T& a, const T& b) {
		return (a < b);
	}
};

template <class RandomAccessIterator>
struct Run {
	Run() {};
	Run(RandomAccessIterator begin, int n)
		: begin(begin), size(n) {};
	RandomAccessIterator begin;
	ui32 size;
};

struct TimSortParametrs{
	enum WhatNeedMerge { XY, YZ, NO };
	virtual int GetMinrun(ui32 numbers) const = 0;
	virtual bool NeedDoubleMerge(const ui32 x_numbers, const ui32 y_numbers) const = 0;
	virtual WhatNeedMerge NeedTripleMerge(const ui32 x_numbers, const ui32 y_numbers, const ui32 z_numbers) const = 0;
};

struct TimSortDefaultParametrs : public TimSortParametrs {
	int GetMinrun(ui32 n) const {
		bool b = 0;
		while (n >= 64) {
			b |= n & 1;
			n >>= 1;
		}
		return n + b;
	}
	bool NeedDoubleMerge(const ui32 x_numbers, const ui32 y_numbers) const {
		return x_numbers >= y_numbers;
	}
	WhatNeedMerge NeedTripleMerge(const ui32 x_numbers, const ui32 y_numbers, const ui32 z_numbers) const {
		//if (z_numbers > y_numbers && x_numbers < y_numbers + z_numbers)
		if (x_numbers < y_numbers)
			return NO;
		else
			if (x_numbers <= z_numbers)
				return XY;
			else
				return YZ;
	}
};

struct UserTimSortParametrs : public TimSortDefaultParametrs {//here is the user's parametrs to TimSort
	int GetMinrun(ui32 n) const {
		bool b = 0;
		while (n >= 64) {
			b |= n & 1;
			n >>= 1;
		}
		return n + b;
	}
	bool NeedDoubleMerge(const ui32 x_numbers, const ui32 y_numbers) const {
		return x_numbers >= y_numbers;
	}
	WhatNeedMerge NeedTripleMerge(const ui32 x_numbers, const ui32 y_numbers, const ui32 z_numbers) const {
		if ((y_numbers <= x_numbers) || (z_numbers < y_numbers + x_numbers))
			if (x_numbers <= z_numbers)
				return XY;
			else
				return YZ;
		else
			return NO;
	}
};


template <class RandomAccessIterator, class Compare>
void Insertsort(RandomAccessIterator left, RandomAccessIterator border, RandomAccessIterator right, Compare cmp) {
	for (vector<VectorType>::iterator i = border; i < right; ++i)
		for (vector<VectorType>::iterator j = i; j > left && cmp(*j, *(j - 1)); --j)
			std::iter_swap((j - 1), j);
}

template <class RandomAccessIterator>
void Reverse(RandomAccessIterator left, RandomAccessIterator right) {
	while (left < right)
		std::iter_swap((left++), (right--));
}

void Print(vector<VectorType> & OutputVector) {
	for (vector<VectorType>::iterator i = OutputVector.begin(); i != OutputVector.end(); ++i)
		cout << *i << ' ';
	cout << endl;
}

void Input(vector<VectorType> & IVector, const int numbers) {
	//int col, length;
	//cin >> col >> length;
	IVector.resize(numbers);
	for (vector<VectorType> ::iterator i = IVector.begin(); i != IVector.end(); ++i) {
		*i = rand() % 10000;
	};
	/*for (int i = 0; i < col; ++i) {
		std::sort(IVector.begin() + i * numbers / col, IVector.begin() + length + i * numbers / 100);
	}*/
	/*for (vector<VectorType>::iterator i = IVector.begin(); i != IVector.end(); ++i) {
		int length = rand() % 256;
		string s;
		s.resize(length);
		for (int j = 0; j < length; ++j)
			s[j] = (rand() % 256);
		*i = s;

	}*/
	/*for (int i = 0; i < col - 1; ++i) {
	std::sort(test.begin() + num * i, test.begin() + num * (i + 1));
	}*/
	/*std::sort(test.begin(), test.begin() + 2 * numbers / 3);
	std::sort(test.begin() + 2 * numbers / 3 + 1, test.end());
	for (int i = 0; i < 2 * numbers / 3; ++i)
	test[i] *= 10;*/
}

/*for (vector<VectorType>::iterator i = left1; i != left1 + size1; ++i)
cout << *i << ' ';
cout << endl;
for (vector<VectorType>::iterator i = left2; i != left2 + size2; ++i)
cout << *i << ' ';
cout << endl;
cout << left1 + size1 - left2 << endl;
cout << size1 + size2 << endl;
std::inplace_merge(left1, left1 + size1 , left2 + size2, cmp);*/


template <class RandomAccessIterator, class Compare>
RandomAccessIterator BinFind(RandomAccessIterator n, RandomAccessIterator left, RandomAccessIterator right, Compare cmp) {
	if (left == right) return left;
	if (cmp(*n, *left)) return left;
	if (cmp(*(right - 1), *n)) return right;
	while (left != right - 1) {
		RandomAccessIterator mid = left + (right - left) / 2;
		if (cmp(*n, *mid))
			right = mid;
		else
			left = mid;
	}
	return right;
}


template <class RAit, class Compare> 
void MergeLft(RAit begin, const int size1, RAit mid , const int size2, RAit end,
	Compare comp) {
	const int galoop_run_length = 5;
	typedef typename RAit::value_type vtype;
	int len = mid - begin;
	std::vector<vtype> buf(len);
	std::copy(begin, mid, buf.begin());
	typename std::vector<vtype>::iterator cur = buf.begin();
	bool is_from_buf = true;
	int gallop_length = 0;
	while (cur != buf.end() && mid != end) {
		if (!comp(*mid, *cur)) {
			*begin = *cur;
			++cur;
			++begin;
			if (!is_from_buf) {
				gallop_length = 0;
			}
			++gallop_length;
			if (gallop_length == galoop_run_length) {
				vtype another_next = *mid;
				auto ins = std::lower_bound(cur, buf.end(), another_next, comp);
				if (ins > cur) {
					begin = std::copy(cur, ins, begin);
					cur = ins;
				}
				gallop_length = 0;
			}
			is_from_buf = true;
		}
		else {
			*begin = *mid;
			++mid;
			++begin;
			if (is_from_buf) {
				gallop_length = 0;
			}
			++gallop_length;
			if (gallop_length == galoop_run_length) {
				vtype another_next = *cur;
				auto ins = std::lower_bound(mid, end, another_next, comp);
				if (ins > mid) {
					begin = std::copy(mid, ins, begin);
					mid = ins;
				}
				gallop_length = 0;
			}
			is_from_buf = false;
		}
	}
	while (cur != buf.end()) {
		*begin = *cur;
		++begin;
		++cur;
	}
}

template <class RandomAccessIterator, class Compare>
void MergeLeft(RandomAccessIterator left1, const int size1, RandomAccessIterator left2, const int size2, RandomAccessIterator p, Compare comp) {
	int k1 = 0, k2 = 0; 
	/*typedef typename RandomAccessIterator::value_type VType;
	vector<VType> help_data(size1);
	std::copy(left1, left1 + size1, help_data.begin());
	typename std::vector<VType>::iterator i = help_data.begin();
	while (i != help_data.end() && left2 != left2 + size2) {
		if (!cmp(*left2, *i)) { //help_data[i] <= a[j]
			*(p++) = *(i++);
			++k1;*/
	typedef typename RandomAccessIterator::value_type vtype;
	int len = size1;
	std::vector<vtype> help_data(len);
	std::copy(left1, left1 + size1, help_data.begin());
	typename std::vector<vtype>::iterator i = help_data.begin();
	while (i != help_data.end() && left2 != left2 + size2) {
		if (!comp(*i, *left2)) {
			*p = *i;
			++i;
			++p;
			//cout <<"k1= "<< k1 << ' ';
			k2 = 0;
			if (k1 >= 7) {
				if (i != help_data.end()) {
					auto point = std::lower_bound(i, help_data.end(), left2, comp);
					/*if (point > i) {
						/*
						p = std::copy(i, point, p);
						i = point;
					}*/
					k1 = 0;
				}
			}
		}
		else {
			*(p++) = *(left2++);
			k1 = 0;
			++k2;
			if (k2 >= 7) {
				/*if (left2 != left2 + size2) {
					//RandomAccessIterator point = BinFind(i, j, right2, cmp);
					auto point = std::lower_bound(left2, left2 + size2, i, comp);
					if (point > left2) {
						p = std::copy(left2, point, p);
						left2 = point;
					}
					k2 = 0;
				}*/
			}
		}
	}
	while (i < help_data.end())
		*(p++) = *(i++);
	while (left2 < left2 + size2)
		*(p++) = *(left2++);
}

/*template <class Compare>
void reverse_cmp(Compare cmp) {
	return !cmp;
}*/

template <class RandomAccessIterator, class Compare>
void Merge(RandomAccessIterator left1, const int size1, RandomAccessIterator left2, const int size2, Compare cmp) {
	if (size1 <= size2) {
		MergeLeft(left1, size1, left2, size2, left1, cmp);
	}
	else {
		RandomAccessIterator i = left2 + size2 - 1, p = i, j = left1 + size1;
		std::reverse_iterator<RandomAccessIterator> ri(i);
		std::reverse_iterator<RandomAccessIterator> rj(j);
		std::reverse_iterator<RandomAccessIterator> rp(p);
		MergeLeft(ri, size2, rj, size1, rp, cmp);
	}
}

/*template <class RandomAccessIterator, class Compare>
void Merge(RandomAccessIterator left1, const int size1, RandomAccessIterator left2, const int size2, Compare cmp) {
	if (size1 <= size2) {
		vector<VectorType> help_data(size1);
		std::copy(left1, left1 + size1, help_data.begin());
		RandomAccessIterator i = help_data.begin(), j = left2, p = left1;
		int k1 = 0, k2 = 0;
		while (i != help_data.end() && j != left2 + size2) {
			if (!cmp(*j, *i)) { //help_data[i] <= a[j]
				*(p++) = *(i++);
				++k1;
				//cout <<"k1= "<< k1 << ' ';
				k2 = 0;
				if (k1 >= 7) {
					if (i != help_data.end()) {
						RandomAccessIterator point = BinFind(j, i, help_data.end(), cmp);
						for (RandomAccessIterator v = i; v != point; ++v) {
							*(p++) = *v;
							++i;
						}
						k1 = 0;
					}
				}
			}
			else {
				*(p++) = *(j++);
				k1 = 0;
				++k2;
				if (k2 >= 7) {
					if (j != size2 + left2) {
						RandomAccessIterator point = BinFind(i, j, size2 + left2, cmp);
						for (RandomAccessIterator v = j; v != point; ++v) {
							*(p++) = *v;
							++j;
						}
						k2 = 0;
					}
				}
			}
		}
		while (i < help_data.end())
			*(p++) = *(i++);
		while (j < left2 + size2)
			*(p++) = *(j++);
	}
	else {
		vector<VectorType> help_data(size2);
		std::copy(left2, left2 + size2, help_data.begin());
		RandomAccessIterator i = left1 + size1 - 1, j = help_data.end() - 1, p = left2 + size2 - 1;
		int k1 = 0, k2 = 0;
		bool end_i = 0, end_j = 0;
		while (i >= left1 && j >= help_data.begin()) {
			if (!cmp(*j, *i)) {
				if (j != help_data.begin())
					*(p--) = *(j--);
				else {
					*(p--) = *(j);
					end_j = 1;
					break;
				}
				++k1;
				k2 = 0;
				if (k1 >= 7) {
					if (j >= help_data.begin()) {
						RandomAccessIterator point = BinFind(i, help_data.begin(), j + 1, cmp);
						for (RandomAccessIterator v = j; v > point; --v) {
							*(p--) = *v;
							--j;
						}
						k1 = 0;
					}
				}
			}
			else {
				if (i != left1)
					*(p--) = *(i--);
				else {
					*(p--) = *i;
					end_i = 1;
					break;
				}
				k1 = 0;
				++k2;
				if (k2 >= 7) {
					if (i >= left1) {
						RandomAccessIterator point = BinFind(j, left1, i + 1, cmp);
						for (RandomAccessIterator v = i; v > point; --v) {
							*(p--) = *v;
							--i;
						}
						k2 = 0;
					}
				}
			}
		}
		if (end_i) {
			while (j > help_data.begin())
				*(p--) = *(j--);
			if (!end_j) *p = *j;
		}
		if (end_j) {
			while (i > left1)
				*(p--) = *(i--);
			if (!end_i) *p = *i;
		}
	}
}*/

/*template <class RandomAccessIterator, class Compare>
void Merge(RandomAccessIterator left1, const int size1, RandomAccessIterator left2, const int size2, Compare cmp) {
if (size1 <= size2) {
vector<VectorType> help_data(size1);
std::copy(left1, left1 + size1, help_data.begin());
RandomAccessIterator i = help_data.begin(), j = left2, p = left1;
int k1 = 0, k2 = 0;
while (i != help_data.end() && j != left2 + size2) {
if (!cmp(*j, *i)) { //help_data[i] <= a[j]
*(p++) = *(i++);
++k1;
//cout <<"k1= "<< k1 << ' ';
k2 = 0;
if (k1 >= 7) {
if (i != help_data.end()) {
RandomAccessIterator point = BinFind(j, i, help_data.end(), cmp);
for (RandomAccessIterator v = i; v != point; ++v) {
*(p++) = *v;
++i;
}
k1 = 0;
}
}
}
else {
*(p++) = *(j++);
k1 = 0;
++k2;
if (k2 >= 7) {
if (j != size2 + left2) {
RandomAccessIterator point = BinFind(i, j, size2 + left2, cmp);
for (RandomAccessIterator v = j; v != point; ++v) {
*(p++) = *v;
++j;
}
k2 = 0;
}
}
}
}
while (i < help_data.end())
*(p++) = *(i++);
while (j < left2 + size2)
*(p++) = *(j++);
}
else {
vector<VectorType> help_data(size2);
std::copy(left2, left2 + size2, help_data.begin());
RandomAccessIterator i = left1 + size1 - 1, j = help_data.end() - 1, p = left2 + size2 - 1;
int k1 = 0, k2 = 0;
while (i >= left1 && j >= help_data.begin()) {
if (!cmp(*j, *i)) {
*(p--) = *(j--);
++k1;
k2 = 0;
if (k1 >= 7) {
if (j >= help_data.begin()) {
RandomAccessIterator point = BinFind(i, help_data.begin(), j + 1, cmp);
for (RandomAccessIterator v = j; v > point; --v) {
*(p--) = *v;
--j;
}
k1 = 0;
}
}
}
else {
*(p--) = *(i--);
k1 = 0;
++k2;
if (k2 >= 7) {
if (i >= left1) {
RandomAccessIterator point = BinFind(j, left1, i + 1, cmp);
for (RandomAccessIterator v = i; v > point; --v) {
*(p--) = *v;
--i;
}
k2 = 0;
}
}
}
}
while (j >= help_data.begin())
*(p--) = *(j--);
while (i >= left1)
*(p--) = *(i--);
}
return;
}*/

template <class RandomAccessIterator, class Compare>
void CurrentMerge(std::stack< Run<RandomAccessIterator> >  & run_stack, TimSortParametrs & tim_sort_parametrs, Compare cmp) {
	if (run_stack.size() <= 1)
		return;
	if (run_stack.size() == 2) {
		Run<RandomAccessIterator> x, y;
		x = run_stack.top();
		run_stack.pop();
		y = run_stack.top();
		if (tim_sort_parametrs.NeedDoubleMerge(x.size, y.size)) {
			run_stack.pop();
			Merge(y.begin, y.size, x.begin, x.size, cmp);
			Run<RandomAccessIterator> NewRun(y.begin, y.size + x.size);
			run_stack.push(NewRun);
		}
		else
			run_stack.push(x);
		return;
	}
	while (run_stack.size() > 2) {
		Run<RandomAccessIterator> x, y, z;
		x = run_stack.top();
		run_stack.pop();
		y = run_stack.top();
		run_stack.pop();
		z = run_stack.top();
		run_stack.pop();
		//if (!(x.second + y.second < z.second && y.second > x.second )) (y.size <= x.size) {
		if (tim_sort_parametrs.NeedTripleMerge(x.size, y.size, z.size) == tim_sort_parametrs.NO) {
			run_stack.push(z);
			run_stack.push(y);
			run_stack.push(x);
			break;
		}
		else
			if (tim_sort_parametrs.NeedTripleMerge(x.size, y.size, z.size) == tim_sort_parametrs.XY) {
				Merge(y.begin, y.size, x.begin, x.size, cmp);
				run_stack.push(z);
				Run<RandomAccessIterator> NewRun(y.begin, y.size + x.size);
				run_stack.push(NewRun);
			}
			else {
				Merge(z.begin, z.size, y.begin, y.size, cmp);
				Run<RandomAccessIterator> NewRun(z.begin, y.size + z.size);
				run_stack.push(NewRun);
				run_stack.push(x);
			}
	}
}

template <class RandomAccessIterator, class Compare>
void PartitionAndMerge(std::stack< Run<RandomAccessIterator> > & run_stack, RandomAccessIterator left, RandomAccessIterator right,
	const int min_run, TimSortParametrs & tim_sort_parametrs, Compare cmp) {
	for (RandomAccessIterator i = left, j = left, border_sort = j; i < right - 1, j < right; ++i) {
		if (!cmp(*(i + 1), *i)) {
			while (!cmp(*(i + 1), *i) && i < right - 1)
				++i;
			border_sort = i;
			if (i - j + 1 < min_run) {
				if (i < right && j >= right - min_run)
					i = right - 1;
				else
					i = min_run + j - 1;
			}
		}
		else {
			while (cmp(*(i + 1), *i) && i < right - 1)
				++i;
			border_sort = i;
			Reverse(j, i);
			if (i - j + 1 < min_run) {
				if (i < right && j >= right - min_run)
					i = right - 1;
				else
					i = min_run + j - 1;
			}
		}
		if (i == right - 2)
			++i;
		Insertsort(j, border_sort, i + 1, cmp);
		Run<RandomAccessIterator> x(j, i - j + 1);
		run_stack.push(x);
		CurrentMerge(run_stack, tim_sort_parametrs, cmp);
		j = i + 1;
	}
}

template <class RandomAccessIterator, class Compare = UserCompare<VectorType> >
void Timsort(RandomAccessIterator left, RandomAccessIterator right, TimSortParametrs & tim_sort_parametrs = TimSortDefaultParametrs(), Compare cmp = Compare()) {
	int min_run = tim_sort_parametrs.GetMinrun(std::distance(left, right) + 1);
	//cout << min_run << endl;
	std::stack< Run<RandomAccessIterator> > run_stack;
	std::vector< Run<RandomAccessIterator> > run_index;
	PartitionAndMerge(run_stack, left, right, min_run, tim_sort_parametrs, cmp);
	while (run_stack.size() > 1) {
		Run<RandomAccessIterator> x, y;
		x = run_stack.top();
		run_stack.pop();
		y = run_stack.top();
		run_stack.pop();
		Merge(y.begin, y.size, x.begin, x.size, cmp);
		Run<RandomAccessIterator> NewRun(y.begin, y.size + x.size);
		run_stack.push(NewRun);
	}
	return;
}

void Copy(vector<VectorType> & a, vector<VectorType> & b) {
	a.resize(b.size());
	for (vector<VectorType>::iterator i = b.begin(), j = a.begin(); i < b.end(); ++i, ++j)
		*j = *i;
}

int Check(vector<VectorType> & a, vector<VectorType> & b, const int numbers, const double timsort_time, vector<double>::iterator diff) {
	double start_sort, end_sort;
	start_sort = clock();
	//qs(a, 0, numbers-1);
	std::sort(a.begin(), a.end());
	//Insertsort(a, 0, numbers);
	//mergeSort(a, 0, a.size() - 1);
	end_sort = clock();
	for (vector<VectorType>::iterator i = a.begin(), j = b.begin(); i < a.end(); ++i, ++j)
		if (*i != *j)
			return 1;
	*(diff) = timsort_time / (double(end_sort - start_sort) / CLOCKS_PER_SEC);
	//cout << "Timsort VS Qsort \n";
	//cout << timsort_time << "        " << double(end_sort - start_sort) / CLOCKS_PER_SEC << "     " << endl;
	return 0;
}

int Check1(vector<VectorType> & a)
{
	for (std::vector<VectorType>::iterator i = a.begin(); i < a.end() - 1; ++i)
		if (*i > *(i + 1))
			return 1;
	return 0;
}

int _tmain(int argc, _TCHAR* argv[])
{
	/*vector<double> v;
	std::sort(v.begin(), v.end(), compare());*/
	int count_of_measures;
	cin >> count_of_measures;
	vector<double> difference(count_of_measures);
	int numbers;
	cin >> numbers;
	for (int i = 0; i < count_of_measures; ++i) {
		TimSortDefaultParametrs tim_sort_parametrs;
		UserTimSortParametrs user_parametrs;
		vector<VectorType> mas;
		//cin >> numbers;
		//numbers = i;
		Input(mas, numbers);
		std::vector<VectorType> copy;
		Copy(copy, mas);
		double start_tim, end_tim;

		start_tim = clock();
		/*for (vector<VectorType>::iterator i = mas.begin(); i != mas.end(); ++i)
			cout << *i << ' ';
		cout << endl;*/
		Timsort(mas.begin(), mas.end());
		end_tim = clock();

		if (Check(copy, mas, numbers, double(end_tim - start_tim) / CLOCKS_PER_SEC, difference.begin() + i))
		{
			cout << "NO" << endl;
		}
		/*cout << uk << endl;
		uk = 0;*/
	}
	double sum = 0;
	for (vector<double>::iterator i = difference.begin(); i != difference.end(); ++i)
		sum += *i;
	cout << "average difference is " << sum / count_of_measures << endl;
	cin >> numbers;
	return 0;
}