Thread: Quicksort question

i have been working on an implimentation of quicksort for the past few minutes, and i have what appears to be a correct implimentation of the algorithm, and yet it doesnt quite sort 100%... it works like a dream for a large number of items, but small numbers tend to get sorted with a slight bit of inaccuracy ( the smaller the number of items, the less accurate ). here is the code i have, any ideas what my problem might be?

Code:

template <typename Type>
void Swap( Type &a, Type &b )
{
	Type temp = a;
	a = b;
	b = temp;
}


template <typename Type>
void qSort( Type * array, int size )
{
	if ( size <= 1 )
		return;
 
	int middle = size / 2;
	if ( array[middle] < array[0] )
		Swap( array[middle], array[0] );
	if ( array[size - 1] < array[0] )
		Swap( array[size - 1], array[0] );
	if ( array[size - 1] < array[middle] )
		Swap( array[size - 1], array[middle] );

	Type pivot = array[middle];
	Swap( array[middle], array[size - 1] );


	int i, j;

	for ( i = 0, j = size - 1 ;; )
	{
		while ( array[++i] < pivot );
		while ( pivot < array[--j] );
		if ( i < j )
			Swap( array[i], array[j] );
		else break;
	}

	Swap( array[i], array[size - 1] );

	qSort( &array[0], i - 1 );

	qSort( &array[i + 1], ( size - (i + 1) ) );

}

It's a little late for me to throw my brain into it, so I'll just show you what I use.

Code:

template <class number>
unsigned partition(number section[], unsigned start, unsigned finish, bool (*compare)(number, number) = greater) 
{
 unsigned pivot = start;
 number value = section[pivot];
   for( unsigned index = start + 1; index < finish ; ++index )
     if( !compare( section[index], value ) )
       swap(section[index], section[++pivot]);
  swap(section[start], section[pivot]);
 return pivot;
}

template <class number>
void quicksort(number section[], unsigned start, unsigned finish, bool (*compare)(number, number) = greater) 
{
    if(start < finish) 
  {
   unsigned pivot = partition(section, start, finish, compare);
   quicksort(section, start, pivot, compare);
   quicksort(section, pivot + 1, finish, compare);
  }
 return;
}

template <class number>
void quicksort(number section[], unsigned length, bool (*compare)(number, number) = greater) 
{
 quicksort(section, 0, length, compare);
}