#ifndef H_SORT
#define H_SORT

#include "misc.h"

template<class T>
void swap(T &a, T &b)
{
	T c;

	c = a;
	a = b;
	b = c;
}

template<class T1, class T2>
void sort(T1 *key, T2 *ptr, long first, long last)
{
	long a, b, c;

	if (first >= last)
		return;
	if (last - first == 1)
	{
		if (key[first] > key[last])
		{
			swap(key[first], key[last]);
			swap(ptr[first], ptr[last]);
		}
		return;
	}
	c = (long) randEx(first, last);
	swap(key[c], key[last]);
	swap(ptr[c], ptr[last]);
	do
	{
		a = first;
		b = last;
		while (a < b && key[a] <= key[last])
			a++;
		while (b > a && key[b] >= key[last])
			b--;
		if (a < b)
		{
			swap(key[a], key[b]);
			swap(ptr[a], ptr[b]);
		}
	}
	while (a != b);
	swap(key[a], key[last]);
	swap(ptr[a], ptr[last]);
	sort(key, ptr, first, a - 1);
	sort(key, ptr, a + 1, last);
}

#endif