```package median;

public class Main {
public static void main(String[] args) {
int[] a = { 3, 9, 1, 14, 2, 10, 13, 5, 8, 6, 15, 16, 4, 7, 12, 11 };
System.out.println(median(a));
}

// quicksort method now renamed to median
public static double median(int[] a) {
return quick(a, 0, a.length-1);
}

/*
* The general idea comes in two pieces.
*
* 1. Make sure to perform quicksort-like pivoting only on the side of the remaining
*    data that needs it.  We only need the median in the right place; the rest of the
*    data is extraneous work, so minimize that work.
* 2. If we have an odd number of data, it is easy to tell if we have the median because
*    there is a single middle element of the array.  If we have an even number of data,
*    we need to know if we are at position n/2 or (n/2)-1.  Depending on which side of
*    the median we have landed, we use one iteration of selection sort to get the biggest
*    datum on the left or the smallest datum on the right so we can take the mean of the
*    two data that comprise the median.
*/
public static double quick(int[] a, int left, int right) {
if (right > left) {
int pivotPos = partition(a, left, right);
int middle = a.length/2;

// Test for pivot position.  The first case is if the array length is
// odd with a single middle; the else is for even array length with two middles.
if (a.length % 2 == 1) {
if (pivotPos == middle) return (a[middle]);
} else {  // Even number of elements
// Approach due to Naveen Ram, Nico Diaz-Wahl, and Jonne Kaunisto:
// Once one of the two middle indices has been found, borrow from
// selection sort and select either the minimum value from the right
// side or the maximum value from the left side, depending on which side
// does not contain the found middle index.
//
// pivotPos == middle looks like xxxxxPxxxx
if (pivotPos == middle) {
if (middle == left) return a[middle];
else return (a[middle] + select(a, left, middle-1, 1)) / 2.0;

// pivotPos == middle - 1 looks like xxxxPxxxxx
} else if (pivotPos == middle - 1) {
if (middle == right) return a[middle];
else return (a[middle-1] + select(a, middle, right, 0)) / 2.0;
}
}

// Here is where we make sure to "sort" the elements that move us
// towards the median element(s)
if (pivotPos < middle) {
return quick(a, pivotPos+1, right);
} else {
return quick(a, left, pivotPos-1);
}
// If we ever get to a situation where we are "sorting" one element,
// it must be a middle element
} else {
return a[left];
}
}

public static int partition(int[] a, int left, int right) {
int splitPos = left;
for (int i = left; i < right; i++) {
if (a[i] < a[right]) {
swap(a, i, splitPos);
splitPos++;
}
}
swap(a,splitPos,right);
return splitPos;
}

public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

// select: if minmax = 0, find the min; otherwise find the max
// in the array between indices left and right
public static int select(int[] a, int left, int right, int minmax) {
int returnValue = a[left];
if (minmax == 0) { // find minimum
for (int i = left; i <= right; i++) {
if (a[i] < returnValue) {
returnValue = a[i];
}
}

} else {
for (int i = left; i <= right; i++) {
if (a[i] > returnValue) {
returnValue = a[i];
}
}
}
return returnValue;
}
}
```