C++ quick sort count comparisons

I am working on a project that asks us to implement different sorts and add counter variables to measure the runtime with different array sizes.

My problem is that the output is not the same as the expected output

I already completed the insertion sort and correctly counts the number of comparisons.

I am allowed to use reference parameter.

Any feedback is appreciated

Array Size:          10         100         1000         10000
--------------------------------------------------------------------
Quick sort           16          384         6401        74378

Array Size:          10         100         1000         10000
--------------------------------------------------------------------
Quick Sort           35         630         10292        132882 

[ 935, 942, 697, 299, 382, 579, 408, 181, 366, 505 ] //unsorted
[ 181, 299, 366, 382, 408, 505, 579, 697, 935, 942 ] //sorted

#include <iostream>
#include <stdlib.h>
#include <iomanip>
#include <cmath>
      /******************************/
      /* Start of Quick Sort Algorithm */
      /******************************/



static const int MIN_SIZE  = 10; // Smallest size of an array that quicksort will sort

/**
 * Sorts the items in an array into ascending order.
 */
template<class ItemType>
int insertionSort(ItemType theArray[], int first, int last) {
  int count = 0;
    for (int unsorted = first + 1; unsorted <= last; unsorted++) {
        ItemType nextItem = theArray[unsorted];
        int loc = unsorted;
        while ((loc > first) && (count++,theArray[loc - 1] > nextItem)) {
            theArray[loc] = theArray[loc - 1];
            loc--;
        }
        theArray[loc] = nextItem;
    }
    return count;
}

/**
 * Arranges two specified array entries into sorted order by
 * exchanging them, if necessary.
 * */
template<class ItemType>
void order(ItemType theArray[], int i, int j) {
    if (theArray[i] > theArray[j]) {
        std::swap(theArray[i], theArray[j]);
    }
}

/**
 * Arranges the first, middle, and last entry in an array in sorted order.
 */
template<class ItemType>
int sortFirstMiddleLast(ItemType theArray[], int first, int last) {
    int mid = first + (last - first) / 2;
    order(theArray, first, mid); // Make theArray[first] <= theArray[mid]
    order(theArray, mid, last);  // Make theArray[mid] <= theArray[last]
    order(theArray, first, mid); // Make theArray[first] <= theArray[mid]

    return mid;
}

/**
 * Partitions the entries in an array about a pivot entry for quicksort.
 */
template<class ItemType>
int partition(ItemType theArray[], int first, int last,int &counter) {
    // Choose pivot using median-of-three selection
    int pivotIndex = sortFirstMiddleLast(theArray, first, last);

    // Reposition pivot so it is last in the array
    std::swap(theArray[pivotIndex], theArray[last - 1]);
    pivotIndex = last - 1;
    ItemType pivot = theArray[pivotIndex];

    // Determine the regions S1 and S2
    int indexFromLeft = first + 1;
    int indexFromRight = last - 2;

    bool done = false;
    while (!done) {
        // Locate first entry on left that is >= pivot
        while (theArray[indexFromLeft] < pivot) {
          counter++;//I incremented Count here
          indexFromLeft = indexFromLeft + 1;
        }

        // Locate first entry on right that is <= pivot
        while (theArray[indexFromRight] > pivot) {
          counter++;
          indexFromRight = indexFromRight - 1;
        }

        if (indexFromLeft < indexFromRight) {
            std::swap(theArray[indexFromLeft], theArray[indexFromRight]);
            indexFromLeft = indexFromLeft + 1;
            indexFromRight = indexFromRight - 1;
        }
        else {
            done = true;
        }
    }

    // Place pivot in proper position between S1 and S2, and mark its new location
    std::swap(theArray[pivotIndex], theArray[indexFromLeft]);
    pivotIndex = indexFromLeft;

    return pivotIndex;
}

/**
 * Sorts an array into ascending order. Uses the quick sort with
 * median-of-three pivot selection for arrays of at least MIN_SIZE
 * entries, and uses the insertion sort for other arrays.
 */
template<class ItemType>
int quicksort(ItemType theArray[], int first, int last) {
    int result = 0;
    int counter = 0;
    if (last - first + 1 < MIN_SIZE) {
        result = insertionSort(theArray, first, last);
    }
    else {
        // Create the partition: S1 | Pivot | S2
        int pivotIndex = partition(theArray, first, last,counter);
        // Sort subarrays S1 and S2
         result += quicksort(theArray, first, pivotIndex - 1);
         result += quicksort(theArray, pivotIndex + 1, last);
         result += counter;
    }
    return result; //return final count
}


      /******************************/
      /* Start of Sorting Benchmark  */
      /******************************/
int* makeRandomArray(int n, int seed) {
    srand(seed);
    int * a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = rand() % 1000;
    }
    return a;
}

int main(){
    const int seed = 9000;
    int *a;

    /******************************/
    /* Start of Quick Sort    */
    /******************************/
    std::cout << "Quick sort";

    int n = 10;
    a = makeRandomArray(10, seed);
    std::cout <<std::setw(13)<< quicksort(a, 0, n-1);
    delete[] a;

    n = 100;
    a = makeRandomArray(100, seed);
    std::cout <<std::setw(13)<< quicksort(a, 0, n-1);
    delete[] a;

    n = 1000;
    a = makeRandomArray(1000, seed);
    std::cout <<std::setw(13)<< quicksort(a, 0, n-1);
    delete[] a;

    n = 10000;
    a = makeRandomArray(10000, seed);
    std::cout <<std::setw(13)<< quicksort(a, 0, n-1)<<std::endl;
    delete[] a;

    return 0;
}