Randomized Lomuto quicksort on an array of identical keys

This quicksort chooses a uniformly random pivot and partitions with Lomuto's scheme. What is its running time on an array of n elements that all hold the same value?

main.cpp
int partition(vector<int>& a, int lo, int hi) {
    swap(a[lo + rand() % (hi - lo + 1)], a[hi]);  // random pivot to the end
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) swap(a[i++], a[j]);
    swap(a[i], a[hi]);
    return i;
}

void quicksort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quicksort(a, lo, p - 1);
    quicksort(a, p + 1, hi);
}

43 of 46 in Data Structures & Algorithms