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


#ifndef MERGE_SORT_H
#define MERGE_SORT_H

#include <stddef.h>
#include "merge.H"
#include "insertion_sort.H"
#include "utilities.H"
#include "pap_auxbuffer.H"

template <class Iterator>
void inplaceMergeSort(Iterator first, Iterator last)
{
    if (last - first < 15) {
	insertionSort(first, last);
	return;
    }
    Iterator middle = first + (last - first)/2;
    inplaceMergeSort(first, middle);
    inplaceMergeSort(middle, last);
    inplaceMerge(first, middle, last);
}

template <class Iterator1, class Iterator2>
void mergeSortLoop(Iterator1 first, Iterator1 last, 
		   Iterator2 result, size_t stepSize)
{
    size_t twoStep = 2*stepSize;

    while (last - first >= twoStep) {
        result = mergeCopy(first, first + stepSize,
			   first + stepSize, first + twoStep, result);
        first += twoStep;
    }
    stepSize = min(size_t(last - first), stepSize);

    mergeCopy(first, first + stepSize, first + stepSize, last, result);
}

template <class Iterator>
void chunkInsertionSort(Iterator first, Iterator last, size_t chunkSize)
{
    while (last - first >= chunkSize) {
	insertionSort(first, first + chunkSize);
	first += chunkSize;
    }
    insertionSort(first, last);
}

#define PAP__CHUNK_SIZE 7
	
template <class Iterator, class BufferIterator>
void mergeSortWithBuffer(Iterator first, Iterator last, 
			 BufferIterator buffer)
{
    size_t len = last - first;
    BufferIterator bufferLast = buffer + len;

    size_t stepSize = PAP__CHUNK_SIZE;
    chunkInsertionSort(first, last, stepSize);

    while (stepSize < len) {
	mergeSortLoop(first, last, buffer, stepSize);
	stepSize *= 2;
	mergeSortLoop(buffer, bufferLast, first, stepSize);
	stepSize *= 2;
    }
}

template <class Iterator, class BufferIterator>
void mergeSortAdaptive(Iterator first, Iterator last, 
		       size_t bufferSize, BufferIterator buffer)
{
    size_t len = (last - first + 1)/2;
    Iterator middle = first + len;
    if (len > bufferSize) {
        mergeSortAdaptive(first, middle, bufferSize, buffer);
        mergeSortAdaptive(middle, last, bufferSize, buffer);
    } else {
        mergeSortWithBuffer(first, middle, buffer);
        mergeSortWithBuffer(middle, last, buffer);
    }
    mergeAdaptive(first, middle, last, bufferSize, buffer);
}

template <class Iterator, class T>
void mergeSortAux(Iterator first, Iterator last, T&)
{
    PAP_auxBuffer<T> buffer((last - first + 1) / 2);
    if (buffer.len > 2)
        mergeSortAdaptive(first, last, buffer.len, buffer.ptr);
    else
        inplaceMergeSort(first, last);
}

template <class Iterator>
void stableSort(Iterator first, Iterator last)
{
    mergeSortAux(first, last, *first);
}

#endif