#ifndef _SORT_BLADEZOR_H_
#define _SORT_BLADEZOR_H_

#include <iostream>

//
//	Title: Bladezor's extremely overcomplicated sort algorithm. 
//
//	Description: I combined various algorithms together such as quick sort and heap sort to come up
//				 with something smart and fast. It's relatively good at handling quick-sort killers.
//

const int MAX_DEPTH = 1000;
bool IsSorted = false;

void swapIndices( int *x, int *y )
{
	int temp = *x;
	*x = *y;
	*y = temp;
}

bool isIncreasing( int *data, int length )
{
	for( int i = 0; i < length; i++ )
	{
		if( i + 1 < length )
		{
			if( *(data + i) == *(data + i + 1) )
			{
				return false;
			}
		}

		if( *(data + i) < *(data) )
		{
			return false;
		}
	}

	return true;
}

bool isDecreasing( int *data, int length )
{
	for( int i = 0; i < length; i++ )
	{	
		if( i+1 < length )
		{
			if( *(data +i ) == *(data + i + 1) )
			{
				return false;
			}
		}

		if( *(data + i) > *(data) )
		{
			return false;
		}
	}

	return true;
}

bool isSame( int *data, int length )
{
	for( int i = 1; i < length; i++ )
	{
		if( *(data + i) != *(data) )
		{
			return false;
		}
	}

	return true;
}

void reverse( int *data, int length )
{
	int left = 0;
	int right = length - 1;

	while( left < right )
	{
		swapIndices( &*(data + left), &*(data + right) );
		left++;
		right--;
	}
}

void siftDown( int *data, int root, int bottom )
{
	int done, maxChild, temp;

	done = 0;
	while ( ( root * 2 <= bottom ) && ( !done ) )
	{
		if ( root * 2 == bottom )
			maxChild = root * 2;
		else if ( *(data + (root * 2) ) > *(data + (root * 2) + 1) )
			maxChild = root * 2;
		else
			maxChild = root * 2 + 1;

		if ( *(data + root) < *(data + maxChild) )
		{
			temp = *(data + root);
			*(data + root) = *(data + maxChild);
			*(data + maxChild) = temp;
			root = maxChild;
		}
		else
		{
			done = 1;
		}
	}
}

void bladeSort( int *data, int start, int end )
{
	if( end > start + 1 )
	{
		int pivot = *(data + start);
		int l = start + 1;
		int r = end;

		while( l < r )
		{
			if( *(data + l) < pivot )
				l++;
			else
			{
				swapIndices(&*(data + l), &*(data + --r));
			}
		}

		swapIndices(&*(data + --l), &*(data + start));
		bladeSort(data, start, l);
		bladeSort(data, r, end);
	}

	IsSorted = true;
}

void heapSort( int *data, int length )
{
	int i, temp;

	for ( i = (length / 2)-1; i >= 0; i-- )
		siftDown(data, i, length);

	for ( i = length-1; i >= 1; i-- )
	{
		temp = data[0];
		*(data) = *(data + i);
		*(data + i) = temp;
		siftDown( data, 0, i-1 );
	}
}

bool Same = true;
bool Increasing = true;
bool Decreasing = true;

void sort_bladezor( int *data, int length )
{
	Same = isSame( data, length );

	if( Same )
	{
		return;
	}

	Increasing = isIncreasing( data, length );
	Decreasing = isDecreasing( data, length );
	IsSorted = false;

	if( Decreasing && !Same )
	{
		reverse( data, length );
		return;
	}
	else
	if( Increasing && !Same )
	{
		return;
	}	
	if( 
		!Same &&
		!Increasing &&
		!Decreasing
	  )
	  if( length < MAX_DEPTH * 2 && !IsSorted )
	  {
		  bladeSort( data, 0, length );
		  IsSorted = true;
		  return;
	  }
	  else if( length >= MAX_DEPTH && !IsSorted )
	  {
		  heapSort( data, length );
		  return;
	  }
}

#endif