I am trying to optimize my quicksort by estimating the median. However, I seem to be doing more than linear time in finding it. Can someone help me figure this out? Below is the question:

Below is my code:

And just in case this way is better here's the code copied and pasted:

/PART2

//Sorts through an array and puts them in order.

//This part handles all the recurssion

public static int quickSort2 (int A[],int p, int r) {

if (p

int q = partition2(A, p, r);

quickSort2 (A, p, q-1);

quickSort2 (A, q+1, r);

}

return p;

}//End of quickSort1

//Sorts section of the array that is given

public static int partition2 (int A[],int p, int r) {

int x,s;

int m = (p+r)/2;

int i = p - 1;

//Estimate the median

//m is in the middle

if ( (m>p && mr && m

x = A[m];

s = m;}

//p is in the middle

if ( (p>r && pm && p

x = A[p];

s = p;}

//r is in the middle

else {

x = A[p];

s = p;}

int temp1 = A[s];

A [s] = A [r];

A [r] = temp1;

//Partician algorithm

for (int j = p; j

if (A[j]

i++;

//exchange A[i] with A[j]

int temp = A[i];

A [i] = A [j];

A [j] = temp;

}//End of if

}//End of for

//Exchange A[i+1] with A[j]

int temp = A[i+1];

A [i+1] = A [r];

A [r] = temp;

return i+1;

}//End of partition

Thank you for your help!

2. Considering the AIp], A[r], and Al(ptr)/2] elements of each subproblem and then choosing the middle one as the pivot. (You will need to change a few lines in Partition)