// see sortall.h

// ***************************
//
// some of the sort functions here are implemented twice to
// better illustrate how the Comparer template parameter is used.
// In "production" versions, there would only be one sort, which would
// use the Comparer template parameter and which would be called by
// a one line version of a sort function without the Comparer
// parameter --- see the SelectionSort function for how this is done
// both InsertionSort and MergeSort use duplicated code
//
// ***************************


const int CUTOFF = 20;               // used in quick/merge sorts 

template <class Type>
void Swap(apvector<Type> & v,int j, int k)
// precondition:  v[j] references value A, v[k] references value B 
// postcondition: v[k] references value B, v[k] references value A 
{
    Type temp = v[j];
    v[j] = v[k];
    v[k] = temp;
}


template <class Type, class Comparer>
void Insert(apvector<Type> & a ,int left,int right, const Comparer & comp)
// precondition: left <= right
// postcondition: a[left] <= ... <= a[right]
//     
// standard insertion sort between left/right
// for use in small quick/merge cases as well
{
    int k,loc;
    Type hold;
    
    for(k=left+1;k<=right;k++) 
    {
        // shift elements to make room for a[k]
        
        hold = a[k];   // insert this element
        loc = k;       // location for insertion
        while (left < loc && comp.compare(hold,a[loc-1]) < 0)
        {
            a[loc] = a[loc-1];
            loc--;
        }
        a[loc] = hold;
    }
}

template <class Type, class Comparer>
void InsertSort(apvector<Type> & a, int size, 
                const Comparer & comp)
// precondition: size = # of elements of a
// postcondition: a is sorted
//
// uses insertion sort     
{
    Insert(a,0,size-1,comp);
}

template <class Type>
void Insert(apvector<Type> & a ,int left,int right)
// precondition: left <= right
// postcondition: a[left] <= ... <= a[right]
//     
// standard insertion sort between left/right
// for use in small quick/merge cases as well
{
    int k,loc;
    Type hold;
    
    for(k=left+1;k<=right;k++) 
    {
        // shift elements to make room for a[k]
        
        hold = a[k];   // insert this element
        loc = k;       // location for insertion
        while (left < loc  && hold < a[loc-1])
        {
            a[loc] = a[loc-1];
            loc--;
        }
        a[loc] = hold;
    }
}

template <class Type>
void InsertSort(apvector<Type> & a, int size)
// precondition: size = # of elements of a
// postcondition: a is sorted
//
// uses insertion sort     
{
    Insert(a,0,size-1);
}

template <class Type,class Comparer>
void SelectSort(apvector<Type> & a, int size, const Comparer & comp)
// precondition: size = # of elements of a
// postcondition: a is sorted
//     
// standard selection sort
{
    int j,k,min;
    
    for(j=0; j< size-1;j++)
    {
        min = j;
        for(k=j+1; k<size; k++)
        {
            if (comp.compare(a[k],a[min]) < 0)
            {
                min = k;
            }
        }
        Swap(a,min,j);
    }
}

template <class Type>
void SelectSort(apvector<Type> & a, int size)
// precondition: size = # of elements of a
// postcondition: a is sorted
//     
// standard selection sort
{
	SelectSort(a,size,Comparer<Type>());
}


template <class Type>
void BubbleSort(apvector<Type> & a, int n)
// precondition: n = # of elements in a
// postcondition: a is sorted
//                note: this is a dog of a sort     
{
    int j,k;
    for(j=n-1; j > 0; j--)
    {
		// find largest element in 0..k, move to a[j]
		for(k=0; k < j; k++)
    	{
	    	if (a[k+1] < a[k])
            {
				Swap(a,k,k+1);
	   		}
		}	
    }
}

template <class Type>
void ShellSort(apvector<Type> & a, int n)
// precondition: n = # elements in a
// postcondition: a is sorted
//     
// shell sort using Hibbard increments, see Weiss "Algorithms, Data Structures and
// Problem Solving with C++"     
{
    int h,j,k,loc,increment;
    Type hold,temp;

    for(h=1; h <= n/2; h *= 2 )
    {
        // found power of 2 closest to n/2
    }
        
    h--;            // went past n/2 in loop guard

	while (h > 0)
    {
        // insertion sort using jumps of 'size' h, see InsertSort above
        
        for(k=h; k < n; k++) 
        {
            hold = a[k];
            loc = k;
            while (h <= loc && hold < a[loc-h])
            {
                a[loc] = a[loc-h];
                loc -= h;
            }
            a[loc] = hold;
        }
        
        h /= 2;
    }
}

template <class Type>
void Merge(apvector<Type> & a, apvector<Type> & b, int left,int mid,int right)
// precondition: a sorted from a[left] ... a[mid] and from
//               a[mid+1] to a[right]
//               extra storage passed in as vector b
// postcondition: a sorted from a[left] ... a[right]     
{
    int lk=left;                          // a's left index 
    int rk = mid+1;                       // a's right index 
    int bk = left;                        // b's index

    while (lk <= mid && rk <= right)      // both parts non-empty?
    {
        if (a[lk] <= a[rk])
        {
            b[bk] = a[lk];
            lk++;
        }
        else
        {
            b[bk] = a[rk];
            rk++;
        }
        bk++;
    }
        // finish any leftovers in a (only one of loops below executes)
    
    while (lk <= mid)
    {
        b[bk] = a[lk];
        bk++;
        lk++;
    }
    while(rk <= right)
    {
        b[bk] = a[rk];
        bk++;
        rk++;
    }
    
        // copy b back to a
    
    for(lk=left; lk <= right; lk++)
    {
    	a[lk] = b[lk];
    }
}

template <class Type, class Comparer>
void Merge(apvector<Type> & a, apvector<Type> & b, int left,int mid,int right,
           const Comparer & comp)
// precondition: a sorted from a[left] ... a[mid] and from
//               a[mid+1] to a[right]
//               extra storage passed in as vector b
// postcondition: a sorted from a[left] ... a[right]     
{
    int lk=left;                          // a's left index 
    int rk = mid+1;                       // a's right index 
    int bk = left;                        // b's index

    while (lk <= mid && rk <= right)      // both parts non-empty?
    {
        if (comp.compare(a[lk],a[rk]) <= 0)
        {
            b[bk] = a[lk];
            lk++;
        }
        else
        {
            b[bk] = a[rk];
            rk++;
        }
        bk++;
    }
        // finish any leftovers in a (only one of loops below executes)
    
    while (lk <= mid)
    {
        b[bk] = a[lk];
        bk++;
        lk++;
    }
    while(rk <= right)
    {
        b[bk] = a[rk];
        bk++;
        rk++;
    }
    
        // copy b back to a
    
    for(lk=left; lk <= right; lk++)
    {
    	a[lk] = b[lk];
    }
}


template <class Type, class Comparer>
void DoMerge(apvector<Type> & a, apvector<Type> & temp, int left,int right,
             const Comparer & comp)
// postcondition: a[left] <= ... <= a[right],
//                temp.length() == a.length(), temp is temp array for merging    
{
    int mid = (left+right)/2;
    
    if (right - left > CUTOFF)
    {
        DoMerge(a, temp, left,mid,comp);
        DoMerge(a, temp, mid+1,right,comp);
        Merge(a, temp, left,mid,right,comp);
    }
    else
    {
        Insert(a,left,right,comp);
    }
}

template <class Type>
void MergeSort(apvector<Type> & a,int n)
{
    MergeSort(a, n, Comparer<Type>());
}


template <class Type, class Comparer>
void MergeSort(apvector<Type> & a, int n, const Comparer & comp)
{
	apvector<Type> temp(a.length());
	DoMerge(a,temp,0,n-1,comp);
}


template <class Type>
int Median(apvector<Type> & a,int first,int last)
// postcondition: returns index of median element of
//            a[first],a[last],a[mid], mid = (first+last)/2
{
    int mid=(first+last)/2;

    if (a[first] < a[mid])
    {
        if (a[mid] < a[last])          return mid;
        else if (a[first] < a[last])   return last;
        else                           return first;
    }
    else
    {
        if (a[first] < a[last])        return first;
        else if (a[last] < a[mid])     return mid;
        else                           return last;
    }
}

template <class Type>
int Pivot(apvector<Type> & a,int first,int last)
// postcondition: returns piv such that
//                first <= k <= piv, a[k] <= a[piv]
//                piv < k <= last, a[piv] < a[k]                
// standard Bently/ola pivot routine
{
    int k,p=first;
    Type piv;
    
    Swap(a,first,Median(a,first,last));
    
    piv = a[first];
    
    for(k=first+1;k<=last;k++)
    {
        if (a[k] <= piv)
        {
            p++;            
            Swap(a,k,p);
        }
    }
    Swap(a,p,first);
    return p;
}

template <class Type>
void Quick(apvector<Type> & a,int first,int last)
// postcondition: a[first] <= ... <= a[list]     
{
    int piv;
    
    if (last - first > CUTOFF)
    {
        piv = Pivot(a,first,last);
        Quick(a,first,piv-1);
        Quick(a,piv+1,last);
    }
    else
    {
        Insert(a,first,last);
    }
}

template <class Type>
void QuickSort(apvector<Type> & a, int size)
// precondition: size = # of elements of a
// postcondition: a is sorted     
{
    Quick(a,0,size - 1);
}