#ifndef _INCLUDED_L3_SORT_H
#define _INCLUDED_L3_SORT_H

// *Sorting methods comparison* Copyright (C) Krzysztof Bosak, 1999-12-30...2000-06-16
// All rights reserved.
// kbosak@box43.pl
// http://www.kbosak.prv.pl

// ALWAYS: n == length_of_string_to_sort

#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "l3_array.h"
#include "l3_heap.h"
#include "l3_ptr.h"
#include "l3_str.h"
#include "l3_rand.h"
#include "l3_tool.h"

//typedef char TEST_TYPE;
//typedef int TEST_TYPE;
//typedef double TEST_TYPE;
typedef ContainerTester TEST_TYPE;

template <class array_container>
void RemoveRepetitionsFromSortedVector(array_container& vec)
{
	if(vec.empty())
	{
		return;
	}
	int write=1;
	for(int read=1; read<vec.size(); read++)
	{
		if(! (vec[write-1]==vec[read]))
		{
			vec[write]=vec[read];
			write++;
		}
	}
	vec.resize(write);
}

template <class object_type>
void ShellSort(object_type * const arr, int n)
{
	const int SHELLSORT_STEPS[]={1, 2, 4, 8, 16, 32, 64, 128, 256, 1024, 2048, 4096};
	const double _log_2_inv=3.3219280948873623478703194294894;//1./log(2);
	const int ind=static_cast<int>(log(n)*_log_2_inv);
	assert(ind>=0);
	assert(SHELLSORT_STEPS[ind]<=n);
	assert(static_cast<size_t>(ind) < sizeof(SHELLSORT_STEPS)/sizeof(SHELLSORT_STEPS[0]));
	for(int gapcounter=ind; gapcounter>=0; gapcounter--)
	{
		const int gap=SHELLSORT_STEPS[gapcounter];
		//cout<<gap<<',';
		for(int group=0; group<gap; group++)
		{
			for(int i=gap; i<n; i+=gap)
			{
				const object_type t=arr[i];
				int j;
				for(j=i; j>0; j-=gap)
					if(t<arr[j-gap])
						arr[j]=arr[j-gap];
					else
						break;
				arr[j]=t;
			}
		}

	}
}

template<class object_type>
inline void Swap(object_type &a, object_type &b)
{
	const object_type tmp=a;
	a=b;
	b=tmp;
}

template<class object_type>
inline void BubbleSort(object_type * const arr, int n)
{
	assert(arr!=NULL);
	assert(n>=1);
	for(int i=0; i<n; i++)
		for(int j=n-1; j>i; j--)
			if(arr[j]<arr[j-1])
				Swap(arr[j-1], arr[j]);
}

template<class object_type>
inline void BubbleSortW(object_type * const arr, int n)
{
	assert(arr!=NULL);
	assert(n>=1);
	for(int i=n; i!=0; i--)
		for(int j=1; j<i; j++)
			if(arr[j]<arr[j-1])
					Swap(arr[j], arr[j-1]);
}

template<class object_type>
inline void ShakerSort(object_type * const arr, int n)
{
	assert(arr!=NULL);
	assert(n>=1);
	int left=1, right=n-1, k=n-1;
	do
	{
	int j;
	for(j=right; j>=left; j--)
		if(arr[j]<arr[j-1])
		{
			Swap(arr[j-1],arr[j]);
			k=j;
		}
	left=k+1;
	for(j=left; j<=right; j++)
		if(arr[j]<arr[j-1])
		{
			Swap(arr[j-1],arr[j]);
			k=j;
		}
	right=k-1;
	}while (left<=right);
}

template<class object_type>
inline void InsertSortW(object_type * const arr, int n)
{
	assert(arr!=NULL);
	assert(n>=1);
	for(int i=1; i<n; i++)
	{
		const object_type t=arr[i];
		int j;
		for(j=i; j>0; j--)
			if(t<arr[j-1])
				arr[j]=arr[j-1];
			else
				break;
		arr[j]=t;
	}
}
template<class object_type>
inline void QuickSortW(object_type * const arr, int n)
{
	assert(arr!=NULL);
	assert(n>=0);// important because of recursive calls
	if(n==0)
		return;// important because of recursive calls
	int i=0, k=n-1;
	object_type t=arr[k>>1];
	do
	{
		while(arr[i]<t)
			i++;
		while(t<arr[k])
			k--;
		if(i>k)
			break;
		if(i!=k)
		{
			const object_type temp=arr[i];
			arr[i]=arr[k];
			arr[k]=temp;
		}
		k--;
		i++;
	}while(i<=k);
	if(i<n)
		QuickSortW(arr+i, n-i);
	if(k!=0)
		QuickSortW(arr, k+1);
}

template<class object_type>
inline void _QuickSortW2(object_type * const arr, int n)
{
	assert(arr!=NULL);
	assert(n>=0);// important because of recursive calls
	if(n<=30)
		return;// important because of recursive calls
	int i=0, k=n-1;
	object_type t=arr[k>>1];
	do
	{
		while(arr[i]<t)
			i++;
		while(t<arr[k])
			k--;
		if(i>k)
			break;
		if(i!=k)
		{
			const object_type temp=arr[i];
			arr[i]=arr[k];
			arr[k]=temp;
		}
		k--;
		i++;
	}while(i<=k);
	if(i<n)
		_QuickSortW2(arr+i, n-i);
	if(k!=0)
		_QuickSortW2(arr, k+1);
}

template<class object_type>
inline void QuickSortW2(object_type * const arr, int n)
{
	_QuickSortW2(arr, n);
	InsertSortW(arr, n);
}

template<class object_type>
inline void HeapSortW(object_type * const arr, int n)
{
	assert(arr!=NULL);
	assert(n>=1);
	int array_index;
	for(array_index=1; array_index<n; array_index++)
	{
		int	child=array_index;
		int parent=(child-1)>>1;
		const object_type t=arr[child];
		while(parent>=0 && arr[parent]<t && child!=0)
		{
			arr[child]=arr[parent];
			child=parent;
			parent=(child-1)>>1;
		}
		assert(child>=0);
		assert(child<n);
		arr[child]=t;
	}
	while(array_index-->1)
	{
		const object_type t=arr[array_index];
		arr[array_index]=arr[0];
		int parent=0;
		int child=1;
		while(child<array_index)
		{
			if(child<array_index-1 && arr[child]<arr[child+1])
				child++;
			if(t<arr[child])
			{
				arr[parent]=arr[child];
				parent=child;
				child=(parent<<1)+1;
			}
			else
				break;
		}
		assert(parent>=0);
		assert(parent<n);
		arr[parent]=t;
	}
}

template<class object_type>
inline void HeapSortW_InsertSortW(object_type * const arr, int n)
{
	assert(arr!=NULL);
	assert(n>=1);
	if(n<=100)
	{
		InsertSortW(arr, n);
		return;
	}
	int size;
	for(size=1; size<n; size++)
	{
		int	child=size;
		int parent=(child-1)>>1;
		const object_type t=arr[child];
		while(parent>=0 && arr[parent]<t && child!=0)
		{
			arr[child]=arr[parent];
			child=parent;
			parent=(child-1)>>1;
		}
		assert(child>=0);
		assert(child<n);
		arr[child]=t;
	}
	while(size-- > 1)
	{
		const object_type t=arr[size];
		arr[size]=arr[0];
		int parent=0;
		int child=1;
		while(child<size)
		{
			if(child<size-1 && arr[child]<arr[child+1])
				child++;
			if(t<arr[child])
			{
				arr[parent]=arr[child];
				parent=child;
				child=(parent<<1)+1;
			}
			else
				break;
		}
		assert(parent>=0);
		assert(parent<n);
		arr[parent]=t;
	}
}

template<class object_type>
inline void HeapSort(object_type * const arr, int n)
{
	assert(arr!=NULL);
	assert(n>=1);
	growing_arrayheap<object_type> HEAP;
	HEAP.setsize(n+1);
	int i;
	for(i=0; i<n; i++)
		HEAP.push(arr[i]);
	i--;
	do
	{
		arr[i]=HEAP.top();
		HEAP.pop();
	}while(i--);
}

template<class object_type>
inline void HeapSortNR(object_type * const arr, int n)
{
	assert(arr!=NULL);
	assert(n>=1);
	if(n==1)
		return;
	int l=(n>>1)+1;
	int ir=n;
	int i;
	int j;
	object_type * const ra=&arr[0]-1;// This is allowed by The Standard, NuMega DevPartner is wrong here. This strange array indexing saves operations later in this function.
	//SmartPtr<object_type> ra(&arr[0]-1, &arr[0], n);
	object_type rra;
	for(;;)
	{
		if(l>1)
		{
			--l;
			rra=ra[l];
		}
		else
		{
			rra=ra[ir];
			ra[ir]=ra[1];
			if(--ir==1)
			{
				ra[1]=rra;
				break;
			}
		}
		i=l;
		j=l<<1;
		while(j<=ir)
		{
			if(j<ir && ra[j]<ra[j+1])
				j++;
			if(rra<ra[j])
			{
				ra[i]=ra[j];
				i=j;
				j<<=1;
			}
			else
			{
				break;
			}
		}
		ra[i]=rra;
	}
}

template <class object_type>
void QuickSortNR2(object_type * const arr_arg, const int n)
{
	assert(arr_arg!=NULL);
	assert(n>=1);
	object_type * const arr=arr_arg-1;// This is allowed by The Standard, NuMega DevPartner is wrong here. This strange array indexing saves operations later in this function.
	int i,ir=n,j,k,l=1;
	int jstack=0;
	object_type a;

	const int SWITCH_TO_INSERTSORT=7;
	const int MAX_STACK_SIZE=64;
	//const double factor=2/log(2);
	//const int MAX_STACK_SIZE=static_cast<int>(ceil(log(n)*factor));// 2*log2(N)
	//cout<<'<'<<MAX_STACK_SIZE/n<<'>'<<endl;
	//basearray<int> istack(MAX_STACK_SIZE);// should be static but DLLs...
	int istack[MAX_STACK_SIZE];
	for(;;)
	{
		if(ir-l<SWITCH_TO_INSERTSORT)
		{
			for(j=l+1; j<=ir; j++)
			{
				a=arr[j];
				for(i=j-1; i>=1; i--)
				{
					if(arr[i]<a || arr[i]==a)
					{
						break;
					}
					arr[i+1]=arr[i];
				}
				arr[i+1]=a;
			}

			if(!jstack)
				return;
			ir=istack[jstack];
			l=istack[jstack-1];
			jstack-=2;
		}
		else
		{
			k=(l+ir)>>1;
			PSwap(arr[k],arr[l+1]);
			if(arr[ir]<arr[l+1])
			{
				PSwap(arr[l+1],arr[ir]);
			}
			if(arr[ir]<arr[l])
			{
				PSwap(arr[l],arr[ir]);
			}
			if(arr[l]<arr[l+1])
			{
				PSwap(arr[l+1],arr[l]);
			}
			i=l+1;
			j=ir;
			a=arr[l];
			for(;;)
			{
				do i++; while(arr[i]<a);
				do j--; while(a<arr[j]);
				if(j<i)
					break;
				if(i!=j)// A must to prevent self-assignment.
				{
					PSwap(arr[i],arr[j]);
				}
			}
			arr[l]=arr[j];
			arr[j]=a;
			jstack+=2;

			//cout<<jstack<<' ';
			if(jstack>=MAX_STACK_SIZE)
			{
				cerr<<"PURE QUICKSORT FAILED! WHAT A STRANGE DATASET. SWITCHING TO HEAPSORT."<<endl;
				assert(0);// But we would like to be informed, it is extremely rare.
				HeapSortNR(arr_arg, n);// If recursion too deep, switch to HeapSort!
				return;
			}
			assert(jstack<MAX_STACK_SIZE);
			if(ir-i+1 >= j-l)
			{
				istack[jstack]=ir;
				istack[jstack-1]=i;
				ir=j-1;
			}
			else
			{
				istack[jstack]=j-1;
				istack[jstack-1]=l;
				l=i;
			}
		}
	}
	#undef PSwap
}

#include <algorithm>
template <class object_type>
void STLSort(object_type * const arr_arg, int n)
{
	assert(arr_arg!=NULL);
	assert(n>=1);
	std::sort(arr_arg, &arr_arg[n]);
}

#include <algorithm>
template <class object_type>
void STLStableSort(object_type * const arr_arg, int n)
{
	assert(arr_arg!=NULL);
	assert(n>=1);
	std::stable_sort(arr_arg, &arr_arg[n]);
}

int BUCKETSORT_BUFFER[128];
inline void BucketSort(char * const arr, int n)// Fastest char sorting...
{	// Valid for char of range 0...127
	assert(arr!=NULL);
	assert(n>=1);
	memset(BUCKETSORT_BUFFER, 0, 128*sizeof(int));
	char *tab2=arr+n;
	const char * const tab3=arr;
	do
	{
		tab2--;
		BUCKETSORT_BUFFER[static_cast<unsigned char>(*tab2)]++;
	}while(tab2>tab3);
	unsigned char i=0;
	do
	{
		while(BUCKETSORT_BUFFER[i]!=0)
		{
			BUCKETSORT_BUFFER[i]--;
			*tab2=static_cast<char>(i);
			tab2++;
		}
		i++;
	}while(i<128);
}

/////////////////////////////////////////////////////////////////////////////
#ifdef SORT_TESTING

#define ADD_SORT_FUNCTION(sfun) { (void(*)(TEST_TYPE *,int))(sfun), #sfun },

struct SortingFunction
{
	void (*function)(TEST_TYPE *, int);
	TextString function_name;
};

SortingFunction SORTING_FUNCTIONS[]=
{
//	ADD_SORT_FUNCTION(ShellSort)// O(N^1.27); anyway slow implementation (or weak algorithm...)
//	ADD_SORT_FUNCTION(BubbleSortW)
//	ADD_SORT_FUNCTION(BubbleSort)
//	ADD_SORT_FUNCTION(ShakerSort)// BEST BubbleSort (N^2!)
//	ADD_SORT_FUNCTION(InsertSortW)// BEST O(N^2), weak for ReverseSortedWaveFiller
//	ADD_SORT_FUNCTION(QuickSortW)// Depreferred against heapsorts,
								// O(N*log2(N)) but O(N^2) in pesimistic case, but wins with SortedWaveFiller,
								// ReverseSortedWaveFiller, ConstantFiller
//	ADD_SORT_FUNCTION(HeapSortW)
//	ADD_SORT_FUNCTION(HeapSortW_InsertSortW)
	//ADD_SORT_FUNCTION(HeapSort)// Uses heap container (complex).

	//SortingFunction( (void(*)(TEST_TYPE *,int))(QuickSortNR2), "ddd"),
	ADD_SORT_FUNCTION(QuickSortNR2)//The Best Of All. BEST OF ALL O(N*log2(N)), wins with RandomMessFiller,
									// outperforms GNU qsort in all cases.
	//ADD_SORT_FUNCTION(QuickSortW)
	//ADD_SORT_FUNCTION(QuickSortW2)
	ADD_SORT_FUNCTION(STLSort)// STL

	ADD_SORT_FUNCTION(HeapSortNR)// Most Reliable Of All.
	ADD_SORT_FUNCTION(STLStableSort)// STL

//	ADD_SORT_FUNCTION(BucketSort)// BEST of all for char sorting, DANGER: limited chars <=127
	{NULL, NULL}
};

bool IsSorted(const TEST_TYPE *origchain, const TEST_TYPE *chain, int length, int spectrum_min, int spectrum_width)
{

	const int spectrum_max=spectrum_min+spectrum_width-1;
	int i;
	for(i=0; i<length; i++)
	{
		if(chain[i]<spectrum_min)
		{
			cerr<<"Result out of spectrum (min)\n";
			assert(0);
			exit(1);
		}
		if(spectrum_max<chain[i])
		{
			cerr<<"Result out of spectrum (max)\n";
			assert(0);
			exit(1);
		}
	}
	for(i=1; i<length; i++)
	{
		if(chain[i]<chain[i-1])
			break;
	}
	if(i<length)
	{
		cerr<<"SORTING ERROR:\n";
		cerr.flush();
		int j;
		for(j=0; j<length; j++)
			cerr<<(TEST_TYPE)chain[j]<<'|';
		cerr<<endl;
		//for(j=0; j<i-1; j++)
		//	cerr<<' ';
		//cerr<<"\\/\n";
		assert(0);
		exit(1);
		return false;
	}

	// Tests if all sorted chain elements exists in original unsorted chain.
	basearray<bool> checked;
	checked.setsize(length);
	checked.fill(true);
	for(i=0; i<length; i++)
	{
		bool char_found=false;
		for(int j=0; j<length; j++)
		{
			if(checked[j]==true)
			{
				if(chain[i]==origchain[j])
				{
					checked[j]=false;
					char_found=true;
					break;
				}
			}
		}
		if(char_found==false)
		{
			cerr<<"Sorted chain element not found in original chain!\n";
			assert(0);
			exit(1);
		}
	}
	return true;
}

void TestSort(const SortingFunction * const sfun, int length, int repetitions,
			  int spectrum_min, int spectrum_width, int randomseed=123)
{
	const int spectrum_max=spectrum_min+spectrum_width-1;
	assert(sfun!=NULL);
	assert(length>0);
	assert(repetitions>0);
	assert(spectrum_min<256);
	assert(spectrum_min+spectrum_width<256);
	assert(randomseed>0);
	autoarray<TEST_TYPE> test(length);
	autoarray<TEST_TYPE> orig(length);
	for(int f=0; sfun[f].function!=NULL; f++)
	{
		cout<<sfun[f].function_name<<": ";
		int i;

		cout<<"same,";
		cout.flush();
		for(i=0; i<length; i++)
			test[i]=static_cast<int>(spectrum_min);
		orig=test;
		sfun[f].function(&test[0], length);
		IsSorted(&orig[0], &test[0], length, spectrum_min, spectrum_width);

		cout<<"sort,";
		cout.flush();
		for(i=0; i<length; i++)
			test[i]=static_cast<int>(spectrum_min+static_cast<double>(spectrum_width)*i/length);
		orig=test;
		sfun[f].function(&test[0], length);
		IsSorted(&orig[0], &test[0], length, spectrum_min, spectrum_width);

		cout<<"one,";
		cout.flush();
		for(i=0; i<length; i++)
			test[i]=static_cast<int>(spectrum_min+static_cast<double>(spectrum_width)*i/length);
		test[length/2]=static_cast<int>(spectrum_min+RAND.irandom(spectrum_width));
		orig=test;
		sfun[f].function(&test[0], length);
		IsSorted(&orig[0], &test[0], length, spectrum_min, spectrum_width);

		cout<<"three,";
		cout.flush();
		for(i=0; i<length; i++)
			test[i]=static_cast<int>(spectrum_min+static_cast<double>(spectrum_width)*i/length);
		test[length/2]=static_cast<int>(spectrum_min+RAND.irandom(spectrum_width));
		test[length/4]=static_cast<int>(spectrum_min+RAND.irandom(spectrum_width));
		test[static_cast<int>(length*.75)]=static_cast<int>(spectrum_min+RAND.irandom(spectrum_width));
		orig=test;
		sfun[f].function(&test[0], length);
		IsSorted(&orig[0], &test[0], length, spectrum_min, spectrum_width);

		cout<<"+wave,";
		cout.flush();
		for(i=0; i<length; i++)
			test[i]=static_cast<int>(spectrum_min+i%spectrum_width);
		orig=test;
		sfun[f].function(&test[0], length);
		IsSorted(&orig[0], &test[0], length, spectrum_min, spectrum_width);

		cout<<"-wave,";
		cout.flush();
		for(i=0; i<length; i++)
			test[i]=static_cast<int>(spectrum_max-i%spectrum_width);
		orig=test;
		sfun[f].function(&test[0], length);
		IsSorted(&orig[0], &test[0], length, spectrum_min, spectrum_width);

		cout<<"revsort,";
		cout.flush();
		for(i=0; i<length; i++)
			test[i]=spectrum_max-static_cast<int>(static_cast<double>(spectrum_width)*i/length);
		orig=test;
		sfun[f].function(&test[0], length);
		IsSorted(&orig[0], &test[0], length, spectrum_min, spectrum_width);

		cout<<"rand,";
		cout.flush();
		for(int r=0; r<repetitions; r++)
		{
			for(i=0; i<length; i++)
				test[i]=static_cast<int>(spectrum_min+RAND.irandom(spectrum_width));
			orig=test;
			sfun[f].function(&test[0], length);
			IsSorted(&orig[0], &test[0], length, spectrum_min, spectrum_width);
		}

		cout<<"OK.\n";
		cout.flush();
	}
}

void TestSortAnyLength(const SortingFunction * const sfun, int length, int repetitions,
					   int spectrum_min, int spectrum_width, int randomseed=1234)
{
	cout<<"length=1:\n";
	cout.flush();
	TestSort(sfun, 1, repetitions, spectrum_min, spectrum_width, randomseed);

	cout<<"length=2:\n";
	cout.flush();
	TestSort(sfun, 2, repetitions, spectrum_min, spectrum_width, randomseed);

	cout<<"length=3:\n";
	cout.flush();
	TestSort(sfun, 3, repetitions, spectrum_min, spectrum_width, randomseed);

	cout<<"length="<<(length/2)+1<<":\n";
	cout.flush();
	TestSort(sfun, (length/2)+1, repetitions, spectrum_min, spectrum_width, randomseed);

	cout<<"length="<<length<<":\n";
	cout.flush();
	TestSort(sfun, length, repetitions, spectrum_min, spectrum_width, randomseed);
}

inline void RandomMessFiller(autoarray<TEST_TYPE> &mess, int spectrum_min, int spectrum_width)
{
	assert(spectrum_min<256);
	assert(spectrum_min+spectrum_width<256);
	const int imax=mess.size();
	for(int i=0; i<imax; i++)
		mess[i]=(TEST_TYPE)(spectrum_min+RAND.irandom(spectrum_width));
}

inline void ConstantFiller(autoarray<TEST_TYPE> &mess, int spectrum_min, int spectrum_width)
{
	assert(spectrum_min<256);
	assert(spectrum_min+spectrum_width<256);
	for(int i=0; i<mess.size(); i++)
		mess[i]=spectrum_min;
}

inline void SortedWaveFiller(autoarray<TEST_TYPE> &mess, int spectrum_min, int spectrum_width)
{
	assert(spectrum_min<256);
	assert(spectrum_min+spectrum_width<256);
	int i;
	for(i=0; i<mess.size(); i++)
		mess[i]=spectrum_min;
	const int imax=mess.size();
	for(i=0; i<imax; i++)
		mess[i]=(TEST_TYPE)(spectrum_min+i%spectrum_width);
}

inline void ReverseSortedWaveFiller(autoarray<TEST_TYPE> &mess, int spectrum_min, int spectrum_width)
{
	assert(spectrum_min<256);
	assert(spectrum_min+spectrum_width<256);
	int i;
	for(i=0; i<mess.size(); i++)
		mess[i]=spectrum_min;
	const int imax=mess.size();
	const int spectrum_max=spectrum_min+spectrum_width;
	for(i=0; i<imax; i++)
		mess[i]=(TEST_TYPE)(spectrum_max-i%spectrum_width);
}

void BenchmarkSort(const SortingFunction * const sfun, int length, int repetitions,
			  int spectrum_min, int spectrum_width,
			  void (* const messing_function)(autoarray<TEST_TYPE> &, int, int))
{
	assert(sfun!=NULL);
	assert(length>0);
	assert(repetitions>0);
	assert(spectrum_min<256);
	assert(spectrum_min+spectrum_width<256);
	autoarray<TEST_TYPE> test(length);

	int r;
	//cout<<"Dead time for every benchmark: ";
	cout.flush();
	clock_t dead_clock=clock();
	assert(dead_clock!=static_cast<clock_t>(-1));
	RAND.setseed(321);
	for(r=0; r<repetitions; r++)
		messing_function(test, spectrum_min, spectrum_width);
	const clock_t current_clock=clock();
	assert(current_clock!=static_cast<clock_t>(-1));
	dead_clock=current_clock-dead_clock;
	//const double dead_time=dead_clock/static_cast<double>(CLOCKS_PER_SEC);
	//cout<<dead_time<<"s\n";

	for(int f=0; sfun[f].function!=NULL; f++)
	{
		//cout<<sfun[f].function_name<<": ";
		//cout<<"time: ";
		cout.flush();

		clock_t benchmark_clock=clock();
		assert(benchmark_clock!=static_cast<clock_t>(-1));
		RAND.setseed(321);
		for(r=0; r<repetitions; r++)
		{
			messing_function(test, spectrum_min, spectrum_width);
			sfun[f].function(&test[0], length);
		}
		const clock_t current_clock=clock();
		assert(current_clock!=static_cast<clock_t>(-1));
		benchmark_clock=current_clock-benchmark_clock-dead_clock;
		const double benchmark_time=benchmark_clock/static_cast<double>(CLOCKS_PER_SEC);
		cout<<benchmark_time<<' ';
		cout.flush();
	}
	cout<<endl;
	cout.flush();
}

#undef ADD_SORT_FUNCTION

#endif // SORT_TESTING

#endif // _INCLUDED_L3_SORT_H