Partition

template <class T>
// This function finds the median of the three values from the first, middle, and last elements
// The return type is the template type with an array, a left index, and a right index as parameters
// required for the requested calculation. In our case, this calculation is discerning where to place the
// the pivot in the array so we can begin partitioning it.
T Median3Pivot(T arr[], int left, int right)
{
    //int iMid = (right+left)/2;
    int iMid = left+(right-left)/2;// prevent overflow errors when calculating the middle value
    if(arr[left] > arr[iMid])
    {
        swap(&arr[left], &arr[iMid]);
    }
    if(arr[iMid]> arr[right])
    {
        swap(&arr[iMid], &arr[right]);
    }
    if(arr[left]> arr[iMid])
    {
        swap(&arr[left],&arr[iMid]);
    }

    swap(&arr[iMid], &arr[right-1]);

    return arr[right-1];
}

// Partition helper function so we begin partitioning for our sub-arrays
// Precondition after finding the median of the three entries,
//  the first, middle, and last entries are sorted with respect to each other thus
//  pivot is at array index right-1
template <class T>
int Partition(T arr[], int left, int right, int& iCompCnts)
{
    Median3Pivot(arr, left, right);
    // the two lines below are the ones that select the pivot
    int iPivotIdx = right-1;
    T iPivot = arr[iPivotIdx];

    int i = left+1, j = right-2; // i represents the index from left while j represents the index from right
    bool bDone = false;
    // Bool flag to indicate when we are done the swapping of the elements when we compare the elements arr[i] and arr[j]
    // wrt to pivot
    while(!bDone)
    {
        // Move the pivot point to the right:
        while(arr[i]<iPivot)
        {
            i++;
            iCompCnts++;

#ifdef _DEBUG_CMPT225_ASSIGNMENT3
            s_iCounter++;
#endif
        }

        iCompCnts++;
#ifdef _DEBUG_CMPT225_ASSIGNMENT3
            s_iCounter++;
#endif

        // Move the pivot point to the left:
        while(iPivot<arr[j])
        {
            j--;
            iCompCnts++;

#ifdef _DEBUG_CMPT225_ASSIGNMENT3
                s_iCounter++;
#endif
        }
        iCompCnts++;

#ifdef _DEBUG_CMPT225_ASSIGNMENT3
                s_iCounter++;
#endif
        // if the right temp. pivot is indeed on the right of the
        // left temp. pivot, then swap:
        if (i<j)
        {
            swap(&arr[i], &arr[j]);
            i++;
            j--;
        }
        else    // the loop is done:
            bDone = true;
    }

    // Place pivot point at the right position and marked it too:
    // Don't want to swap elements that are adjacent to each other so we have a three parameter insertion sort guarding
    // against this degenerate case
    swap(&arr[iPivotIdx],&arr[i]);
    iPivotIdx = i;

    return iPivotIdx;
}