/*
 *  MergeSort
 *
 *  21.11.1998, implemented by Michael Neumann (neumann@s-direktnet.de)
 */

# ifndef __MERGESORT_HEADER__
# define __MERGESORT_HEADER__

# include <algorithm>

// Array b[] must have same size like a[]; result is in a[]!
template <class itemType, class indexType=int>
void MergeSort(itemType a[], itemType b[], indexType l, indexType r)
{
    indexType i, j, k, m;

    if(r > l) {
        m = (r+l)/2;
        MergeSort(a,b,l,m);
        MergeSort(a,b,m+1,r);
        for(i=m+1; i>l; --i) b[i-1] = a[i-1];
        for(j=m; j<r; ++j) b[r+m-j] = a[j+1];
        for(k=l; k<=r; ++k) a[k] = (b[i] < b[j]) ?  b[i++] : b[j--];
    }
}

# endif