// Сортировка почти отсортированного массива
		public static void SortOrdered<T>(this List<T> a) where T : IComparable<T> {
			if(a.Count <= 1) return;
			Int32 cnt = a.Count * 2; // Количество дополнительных операций, после которого считаем несортированным
			for(Int32 i = 1; i < a.Count; i++) {
				if(a[i-1].CompareTo(a[i]) > 0) { // a[i-1] > a[i], a[i] надо сдвинуть назад
					if(cnt < 0) { // несортированно
						a.Sort(); // полноценная сортировка
						return;
					}
					// Поиск места вставки
					T x = a[i];
					Int32 r = 0, l = i - 1; 
					while (r < l) {
						cnt--;
						Int32 c = (r + l) / 2;
						Int32 cmp = x.CompareTo(a[c]);
						if(cmp <= 0) { // x <= a[c]
							l = c;
							if (cmp == 0) break;
						} else { // x > a[c]
							r = c + 1;
						}
					}
					// Сдвиг влево [l,i-1]
					cnt -= i - l;
					for(Int32 j = i; j > l; j--) {
						a[j] = a[j-1];
					}
					a[l] = x;
				}
			}
		}

		//Объединение сортированных массивов
		public static List<T> ClueOrdered<T>(List<T> a1, List<T> a2) where T : IComparable<T> {
			Int32 cnt1 = a1.Count, cnt2 = a2.Count, i1 = 0, i2 = 0;
			var ret = new List<T>(cnt1 + cnt2);
			while(i2 < cnt2 || i1 < cnt1) {
				if(i2 == cnt2 || (i1 < cnt1 && a1[i1].CompareTo(a2[i2]) < 0)) {
					ret.Add(a1[i1]);
					i1++;
				} else if(i2 < cnt2) {
					ret.Add(a2[i2]);
					i2++;
				}
			}
			return ret;
		}

#include <windows.h>
#include <stdio.h>

#include <string>
#include <vector>
#include <algorithm>
#include <time.h>

// -------------------------------------------------------
#ifdef _DEBUG
#define TEST_SIZE 20
#else
#define TEST_SIZE 10000000
#endif
// -------------------------------------------------------
int32_t compare_cnt; // Счетчик сравнений
int32_t copy_cnt; // Счетчик копирований
clock_t start;

class item_t {
public:
	char data[10];

	item_t() {}

	item_t(const item_t& b) { *this = b; }

	static int compare(item_t const &a, item_t const &b) {
		compare_cnt++;
		return memcmp(a.data, b.data, sizeof(item_t));
	}

	int compare(item_t const &b) {
		compare_cnt++;
		return memcmp(data, b.data, sizeof(item_t));
	}

	bool operator > (item_t const &b) { return compare(b) > 0; }
	bool operator >= (item_t const &b) { return compare(b) >= 0; }
	bool operator < (item_t const &b) { return compare(b) < 0; }
	bool operator <= (item_t const &b) { return compare(b) <= 0; }
	bool operator == (item_t const &b) { return compare(b) == 0; }
	item_t& operator = (item_t const &b) {
		copy_cnt++;
		memcpy(data, b.data, sizeof(item_t));
		return *this;
	}

	item_t& operator = (int x) {
		_itoa(x, data, 10);
		return *this;
	}

	void swap(item_t &b) {
		item_t t = *this;
		*this = b;
		b = t;
	}

	static void swap(item_t &a, item_t &b) {
		item_t t = a;
		a = b;
		b = t;
	}
};

// -------------------------------------------------------
std::vector<item_t> a(TEST_SIZE); // Тестовый массив

// старт замера
void reset() {
	compare_cnt = 0;
	copy_cnt = 0;
	start = clock();
}

// Вывод текущего состояния
void print() {
	size_t max = a.size() < 20 ? a.size() : 20;
	for (size_t i = 0; i < max; i++) {
		printf("'%s',", a[i].data);
	}
	if (max < a.size()) printf("...");
	printf("\n");
}

// вывод результата
void result(const char* title, std::vector<item_t>* res = NULL) {
	clock_t t = clock() - start;
	printf("%s %d ms %d copies %d compares\n", title, t, copy_cnt, compare_cnt);
	if(res == NULL) {
		if(!std::is_sorted(a.begin(), a.end())) printf("!!! Not sorted\n");
	} else {
		if (!std::is_sorted(res->begin(), res->end())) printf("!!! Not sorted\n");
	}
	static FILE* f = NULL;
	if (f == NULL) {
		f = fopen("result.txt", "w");
	}
	if (f != NULL) {
		fprintf(f, "%s,%d,%d,%d\n", title, t, copy_cnt, compare_cnt);
		fflush(f);
	}
}

// Заполнение тестового массива
void fill() {
	uint32_t k = 1234567;
	for (size_t i = 0; i < a.size(); i++) {
		_itoa(k % (TEST_SIZE * 2), a[i].data, 10);
		k = (k * 65537 + 2017);
	}
	printf("Fill %d OK\n", a.size());
}

// -------------------------------------------------------
// тест qsort()
int compare(const void * a, const void * b) {
	return item_t::compare(*(item_t*)a, *(item_t*)b);
}

__declspec(noinline) void test1() {
	reset();
	qsort(&a[0], a.size(), sizeof(item_t), compare);
	result("qsort()");
}

// -------------------------------------------------------
// тест std::sort()
__declspec(noinline) void test2() {
	reset();
	std::sort(a.begin(), a.end());
	result("std::sort()");
}

// -------------------------------------------------------
// тест quick sort https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F
void quick_sort(item_t* s_arr, int first, int last)
{
	int i = first, j = last;
	item_t x = s_arr[(first + last) / 2];

	do {
		while (s_arr[i] < x) i++;
		while (s_arr[j] > x) j--;

		if (i <= j) {
			if (s_arr[i] > s_arr[j]) item_t::swap(s_arr[i], s_arr[j]);
			i++;
			j--;
		}
	} while (i <= j);

	if (i < last)
		quick_sort(s_arr, i, last);
	if (first < j)
		quick_sort(s_arr, first, j);
}

__declspec(noinline) void test3() {
	reset();
	quick_sort(&a[0], 0, a.size() - 1);
	result("quick_sort()");
}

// -------------------------------------------------------
// тест merge sort https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC

/**
* Сортирует массив, используя рекурсивную сортировку слиянием
* up - указатель на массив, который нужно сортировать
* down - указатель на массив с, как минимум, таким же размером как у 'up', используется как буфер
* left - левая граница массива, передайте 0, чтобы сортировать массив с начала
* right - правая граница массива, передайте длину массива - 1, чтобы сортировать массив до последнего элемента
* возвращает: указатель на отсортированный массив. Из-за особенностей работы данной реализации
* отсортированная версия массива может оказаться либо в 'up', либо в 'down'
**/
item_t* merge_sort(item_t* up, item_t* down, unsigned int left, unsigned int right)
{
	if (left == right)
	{
		down[left] = up[left];
		return down;
	}

	unsigned int middle = (unsigned int)((left + right) * 0.5);

	// разделяй и сортируй
	item_t *l_buff = merge_sort(up, down, left, middle);
	item_t *r_buff = merge_sort(up, down, middle + 1, right);

	// слияние двух отсортированных половин
	item_t *target = l_buff == up ? down : up;

	unsigned int width = right - left, l_cur = left, r_cur = middle + 1;
	for (unsigned int i = left; i <= right; i++)
	{
		if (l_cur <= middle && r_cur <= right)
		{
			if (l_buff[l_cur] < r_buff[r_cur])
			{
				target[i] = l_buff[l_cur];
				l_cur++;
			}
			else
			{
				target[i] = r_buff[r_cur];
				r_cur++;
			}
		}
		else if (l_cur <= middle)
		{
			target[i] = l_buff[l_cur];
			l_cur++;
		}
		else
		{
			target[i] = r_buff[r_cur];
			r_cur++;
		}
	}
	return target;
}

__declspec(noinline) void test4() {
	reset();
	std::vector<item_t> b(TEST_SIZE);
	item_t* r = merge_sort(&a[0], &b[0], 0, a.size() - 1);
	if(r == &a[0]) {
		result("merge_sort()");
	} else {
		result("merge_sort()", &b);
	}
}

//----------------------------------------------------------------------------------
// Моя самодельная Insert sort+

void insert_sort(std::vector<item_t>& a) {
	// Сортировка почти отсортированного массива
	int size = a.size();
	if (size <= 1) return;
	int cnt = size * 2; // Количество дополнительных операций, после которого считаем несортированным
	for (int i = 1; i < size; i++) {
		if (a[i - 1] > a[i]) { // a[i] надо сдвинуть назад
			if (cnt < 0) { // несортированно
				std::sort(a.begin(), a.end()); // полноценная сортировка
				return;
			}
			// Поиск места вставки
			item_t x = a[i];
			int r = 0, l = i - 1;
			while (r < l) {
				cnt--;
				int c = (r + l) / 2;
				int cmp = item_t::compare(x, a[c]);
				if (cmp <= 0) { // x <= a[c]
					l = c;
					if (cmp == 0) break;
				}
				else { // x > a[c]
					r = c + 1;
				}
			}
			// Сдвиг влево [l,i-1]
			cnt -= i - l;
			for (int j = i; j > l; j--) {
				a[j] = a[j - 1];
			}
			a[l] = x;
		}
	}
}

__declspec(noinline) void test5() {
	reset();
	insert_sort(a);
	result("insert_sort()");
}


int main()
{
	printf("Test unordered\n");
	fill();
	print();
	test1();
	fill();
	test2();
	fill();
	test3();
	fill();
	test4();
	fill();
	test5();
	printf("\nTest ordered\n");
	test1();
	test2();
	test3();
	test4();
	test5();

	return 0;
}