write quick sort in java using the median of three. please include comments for each line of code

Divide:

1. Find the pivot (use median-of-three algorithm = (1)

2. Swap the pivot with the last element of the array ((1))

3. For the remaining elements of the array a[0]..a[n-2], define 2 markers: Left and Right. Left and Right markers start from the left side (a[0]) and the right side (a[n-2]) of the array respectively and move toward the center.

4. Marker Left stops if element a[i]>pivot and Marker Right stops if element a[i]

7. Now divide the array into two sub-arrays aleft (a[0], a[1], . . . , a[k-1]), and aright (a[k+1], . . . , a[n1]) ( where aj pivot for every j k 1, and aj pivot for every j i) ((1)) (Note: now you have aleft, pivot, aright)

Conquer: Recursively solve two sub-problems (each of size n/2 if pivot=median of the array) (contributes 2T(n/2) to the running time.) (Recursively = repeat this step until the size of the sub-arrays are 5 or fewer, then sort array using insertion sort)

Combine: Combine the sub-problems by concatenating the aleft, pivot, aright. ((1))