java - How to find the median of a large number of integers (they dont fit in memory) -

i know answer using median of medians can explain how it?

there linear time algorithms this, page might helpful, http://en.wikipedia.org/wiki/selection_algorithm, if still confused ask

basically way selection algorithm works quicksort sorts on side of pivot each time. goal keep partitioning until choose pivot equal index of element trying find. here java code found quickselect:

public static int selectkth(int[] arr, int k) {  if (arr == null || arr.length <= k)   throw new error();   int = 0, = arr.length - 1;   // if == reached kth element  while (from < to) {   int r = from, w = to;   int mid = arr[(r + w) / 2];    // stop if reader , writer meets   while (r < w) {     if (arr[r] >= mid) { // put large values @ end     int tmp = arr[w];     arr[w] = arr[r];     arr[r] = tmp;     w--;    } else { // value smaller pivot, skip     r++;    }   }    // if stepped (r++) need step 1 down   if (arr[r] > mid)    r--;    // r pointer on end of first k elements   if (k <= r) {    = r;   } else {    = r + 1;   }  }   return arr[k]; }