QuickSort on n identical elements.

Suppose the array-based quicksort implementation given in class is applied to an array in which all n elements are identical.

Analyze the runtime of quicksort in this scenario. Give your answer using big-Theta notation and explain clearly how you arrived at your answer (i.e., convince us!)

(The C++ implementation given in class also appears in Appendix B for reference).

Appendix B: QuickSort implementation

void qs(int a[], int l, int r){

int i, j, pivot;

if(r <= l)

return;

if(r==l+1) {

if(a[l] > a[r])

swap(a, l, r);

return;

}

// median of three

int m = (l+r)/2;

if(a[m] < a[l])

swap(a, l, m);

if(a[r] < a[l])

swap(a, r, l);

if(a[r] < a[m])

swap (a, r, m);

swap(a, m, r-1);

pivot = a[r-1];

i = l;

j = r-1;

for(;;){

while(a[++i] < pivot);

while(a[--j] > pivot);

if(i >= j) break;

swap(a, i, j);

}

swap(a, i, r-1); // replace pivot

qs(a, l, i-1);

qs(a, i+1, r);

}

void swap(int a[], int i, int j) {

int tmp;

tmp = a[i];

a[i] = a[j];

a[j] = tmp;

}