/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 */


#ifndef PARTITION_MERGE_SORT_H
#define PARTITION_MERGE_SORT_H

#include <stddef.h>
#include "partition.H"
#include "sort_utilities.H"

template <class T>
class Comp
{
protected:
    T value;
public:
    Comp(T x) : value(x) {}
    int operator()(T x)
    {
	return value - x > 0;
    }
};

template <class Iterator, class BufferIterator, class T>
Iterator stablePartitionAdaptiveAux(Iterator first, Iterator last, T& value,
				    size_t bufferSize, BufferIterator buffer)
{
    return stablePartitionAdaptive(first, last, 
				   Comp<T>(value), bufferSize, buffer);
}   

template <class Iterator, class T>
Iterator inplaceStablePartitionAux(Iterator first, Iterator last, T& value)
{
    return inplaceStablePartition(first, last, Comp<T>(value));
}   

template <class Iterator>
void inplacePartitionMergeSort(Iterator first, Iterator last)
{
	
    if (last - first < 17)
	insertionSort(first, last);
    else {
	Iterator middle = 
	    inplaceStablePartitionAux(first, last, 
				      *randomSelect(first, last));
	inplacePartitionMergeSort(first, middle); 
	inplacePartitionMergeSort(middle, last); 
    }
}
	
template <class Iterator, class BufferIterator>
void partitionMergeSortAdaptive(Iterator first, Iterator last, 
				size_t bufferSize, BufferIterator buffer)
{
    if (last - first > bufferSize) {
	Iterator middle = 
	    stablePartitionAdaptiveAux(first, last, 
				       *randomSelect(first, last),
				       bufferSize, buffer);
	partitionMergeSortAdaptive(first, middle, bufferSize, buffer); 
	partitionMergeSortAdaptive(middle, last, bufferSize, buffer); 
    } else
	mergeSortWithBuffer(first, last, buffer);
}

#endif