Base case for median finding:  Use insertion sort
496842
function insertionSort(d, axis, start, end, boxes, ids) {
  var elemSize = 2 * d
  var boxPtr = elemSize * (start+1) + axis
  for(var i=start+1; i<end; ++i, boxPtr+=elemSize) {
    var x = boxes[boxPtr]
    for(var j=i, ptr=elemSize*(i-1); 
        j>start && boxes[ptr+axis] > x; 
        --j, ptr-=elemSize) {
      //Swap
      var aPtr = ptr
      var bPtr = ptr+elemSize
      for(var k=0; k<elemSize; ++k, ++aPtr, ++bPtr) {
        var y = boxes[aPtr]
        boxes[aPtr] = boxes[bPtr]
        boxes[bPtr] = y
      }
      var tmp = ids[j]
      ids[j] = ids[j-1]
      ids[j-1] = tmp
    }
  }
}
1089098
private int binarySearch(List<SparseItemset> candidates, SparseItemset scratch, int begin, int end) {
    --end;
    while(begin < end) {
      final int mid = (begin + end) >>> 1;
      SparseItemset midVal = candidates.get(mid);
      int cmp = midVal.compareTo(scratch);

      if(cmp < 0) {
        begin = mid + 1;
      }
      else if(cmp > 0) {
        end = mid - 1;
      }
      else {
        return mid; // key found
      }
    }
    return -(begin + 1); // key not found, return next
  }
50184
def median(input=None, configObj=None, editpars=False, **inputDict):
    
    if input is not None:
        inputDict["input"] = input
    else:
        raise ValueError("Please supply an input image")

    configObj = util.getDefaultConfigObj(__taskname__, configObj, inputDict,
                                         loadOnly=(not editpars))
    if configObj is None:
        return

    if not editpars:
        run(configObj)
1233939
private static void quickSortReverse(double[] keys, int[] vals, final int start, final int end) {
    final int len = end - start;
    if(len < INSERTION_THRESHOLD) {
      insertionSortReverse(keys, vals, start, end);
      return;
    }
    final int last = end - 1;

    // Choose pivots by looking at five candidates.
    final int seventh = (len >> 3) + (len >> 6) + 1;
    final int m3 = (start + end) >> 1; // middle
    final int m2 = m3 - seventh;
    final int m1 = m2 - seventh;
    final int m4 = m3 + seventh;
    final int m5 = m4 + seventh;

    // Mixture of insertion and merge sort:
    sortReverse5(keys, vals, m1, m2, m3, m4, m5);

    // Move pivot to the front.
    double pivotkey = keys[m3];
    int pivotval = vals[m3];
    keys[m3] = keys[start];
    vals[m3] = vals[start];

    // The interval to pivotize
    int left = start + 1; // Without pivot
    int right = last; // inclusive

    // This is the classic QuickSort loop:
    while(true) {
      // Move duplicates to right partition, i.e. < here, <= below.
      while(left <= right && keys[left] > pivotkey) {
        left++;
      }
      while(left <= right && pivotkey >= keys[right]) {
        right--;
      }
      if(right <= left) {
        break;
      }
      swap(keys, vals, left, right);
      left++;
      right--;
    }
    // right now points to the last element smaller than the pivot.
    // Move pivot back into the appropriate place
    keys[start] = keys[right];
    vals[start] = vals[right];
    keys[right] = pivotkey;
    vals[right] = pivotval;

    // Recursion when more than one element only:
    if(start + 1 < right) {
      quickSortReverse(keys, vals, start, right);
    }
    int rstart = right + 1;
    // Avoid recursing on duplicates of the pivot:
    while(rstart < last && keys[rstart] >= keys[right]) {
      rstart++;
    }
    // Recurse when _more_ than 1 element only
    if(rstart < last) {
      quickSortReverse(keys, vals, rstart, end);
    }
  }
873444
def median(ls):
    
    ls = sorted(ls)
    return ls[int(floor(len(ls)/2.0))]
1058759
private void insertionSort(int left, int right) {
        for (int p = left + 1; p <= right; p++) {
            byte[] tmpRange = ranges[p];
            String tmpFilename = filenames[p];

            int j;
            for (j = p; j > left && KeyUtils.compareKey(tmpRange, ranges[j - 1]) < 0; j--) {
                ranges[j] = ranges[j - 1];
                filenames[j] = filenames[j - 1];
            }
            ranges[j] = tmpRange;
            filenames[j] = tmpFilename;
        }
    }
813175
def weighted_median(data, weights=None):
    """"""
    if weights is None:
        return median(data)
    midpoint = 0.5 * sum(weights)
    if any([j > midpoint for j in weights]):
        return data[weights.index(max(weights))]
    if any([j > 0 for j in weights]):
        sorted_data, sorted_weights = zip(*sorted(zip(data, weights)))
        cumulative_weight = 0
        below_midpoint_index = 0
        while cumulative_weight <= midpoint:
            below_midpoint_index += 1
            cumulative_weight += sorted_weights[below_midpoint_index-1]
        cumulative_weight -= sorted_weights[below_midpoint_index-1]
        if cumulative_weight - midpoint < sys.float_info.epsilon:
            bounds = sorted_data[below_midpoint_index-2:below_midpoint_index]
            return sum(bounds) / float(len(bounds))
        return sorted_data[below_midpoint_index-1]
1090666
private static void insertionSort(int array[], int offset, int end) {
		for (int x=offset; x<end; ++x) {
			for (int y=x; y>offset && array[y-1]>array[y]; y--) {
				int temp = array[y];
				array[y] = array[y-1];
				array[y-1] = temp;
			}
		}
	}
84470
public static char median(final char a, final char b, final char c) {
        if ((a >= b && a <= c) || (a >= c && a <= b)) {
            return a;
        } else if ((b >= a && b <= c) || (b >= c && b <= a)) {
            return b;
        } else {
            return c;
        }
    }
1242564
def numpy_weighted_median(data, weights=None):
    """"""
    import numpy as np
    if weights is None:
        return np.median(np.array(data).flatten())
    data, weights = np.array(data).flatten(), np.array(weights).flatten()
    if any(weights > 0):
        sorted_data, sorted_weights = map(np.array, zip(*sorted(zip(data, weights))))
        midpoint = 0.5 * sum(sorted_weights)
        if any(weights > midpoint):
            return (data[weights == np.max(weights)])[0]
        cumulative_weight = np.cumsum(sorted_weights)
        below_midpoint_index = np.where(cumulative_weight <= midpoint)[0][-1]
        if cumulative_weight[below_midpoint_index] - midpoint < sys.float_info.epsilon:
            return np.mean(sorted_data[below_midpoint_index:below_midpoint_index+2])
        return sorted_data[below_midpoint_index+1]
539821
function findHighIndexInSortedArray(ary, mapFn, loVal, hiVal) {
    var lo = loVal || 0;
    var hi = hiVal !== undefined ? hiVal : ary.length;
    while (lo < hi) {
      var mid = (lo + hi) >> 1;
      if (mapFn(ary[mid]) >= 0)
        lo = mid + 1;
      else
        hi = mid;
    }
    return hi;
  }
1267941
private int findSmallestFrom(int startId, List<String> sortFlds, List<Integer> sortDirs) {
		int minId = startId;
		moveToId(startId);
		while (super.next()) {
			int id = currentId();
			if (minId < 0 || compareRecords(minId, id, sortFlds, sortDirs) > 0)
				minId = id;
			moveToId(id);
		}
		return minId;
	}
549673
def median_high(data):
    
    data = sorted(data)
    n = len(data)
    if n == 0:
        raise StatisticsError("no median for empty data")
    return data[n // 2]
739743
public static int median(final Object[] a, int start, int end, Comparator<Object> cmp)
    {
        final int m = start + ((end - start) / 2);
        int smallest = start;

        if (cmp.compare(a[smallest], a[m]) > 0) {
            smallest = m;
        }
        if (cmp.compare(a[smallest], a[end]) > 0) {
            smallest = end;
        }

        if (smallest == start) {
            return (cmp.compare(a[m], a[end]) < 0) ? m : end;
        }
        if (smallest == m) {
            return (cmp.compare(a[start], a[end]) < 0) ? start : end;
        }
        return (cmp.compare(a[start], a[m]) < 0) ? start : m;
    }
502632
@Override
    public int find(int x) {
        int curr = x;
        int currp = p[curr];
        while (curr != currp) {
            curr = currp;
            currp = p[curr];
        }
        return curr;
        // TODO: use path compression/halving/...?
    }
138010
private static void quickSort(int[] data, final int start, final int end, IntComparator comp) {
    final int len = end - start;
    final int last = end - 1;
    if(len < INSERTION_THRESHOLD) {
      insertionSort(data, start, end, comp);
      return;
    }

    // Choose pivots by looking at five candidates.
    final int seventh = (len >> 3) + (len >> 6) + 1;
    final int m3 = (start + end) >> 1; // middle
    final int m2 = m3 - seventh;
    final int m1 = m2 - seventh;
    final int m4 = m3 + seventh;
    final int m5 = m4 + seventh;

    // Explicit (and optimal) sorting network for 5 elements
    // See Knuth for details.
    sort5(data, m1, m2, m3, m4, m5, comp);

    // Choose the 2 and 4th as pivots, as we want to get three parts
    // Copy to variables v1 and v3, replace them with the start and end
    // Note: do not modify v1 or v3 until we put them back!
    final int lpivot = data[m2];
    final int rpivot = data[m4];
    data[m2] = data[start];
    data[m4] = data[last];

    // A tie is when the two chosen pivots are the same
    final boolean tied = comp.compare(lpivot, rpivot) == 0;

    // Insertion points for pivot areas.
    int left = start + 1;
    int right = last - 1;

    // Note: we merged the ties and no ties cases.
    // This likely is marginally slower, but not at a macro level
    // And you never know with hotspot.
    for(int k = left; k <= right; k++) {
      final int tmp = data[k];
      final int c = comp.compare(tmp, lpivot);
      if(c == 0) {
        continue;
      }
      else if(c < 0) {
        // Traditional quicksort
        data[k] = data[left];
        data[left] = tmp;
        left++;
      }
      else if(tied || comp.compare(tmp, rpivot) > 0) {
        // Now look at the right. First skip correct entries there, too
        while(true) {
          final int tmp2 = data[right];
          if(comp.compare(tmp2, rpivot) > 0 && k < right) {
            right--;
          }
          else {
            break;
          }
        }
        // Now move tmp from k to the right.
        data[k] = data[right];
        data[right] = tmp;
        right--;
        // Test the element we just inserted: left or center?
        if(comp.compare(data[k], lpivot) < 0) {
          final int tmp2 = data[k];
          data[k] = data[left];
          data[left] = tmp2;
          left++;
        } // else: center. cannot be on right.
      }
    }
    // Put the pivot elements back in.
    // Remember: we must not modify v1 and v3 above.
    data[start] = data[left - 1];
    data[left - 1] = lpivot;
    data[last] = data[right + 1];
    data[right + 1] = rpivot;
    // v1 and v3 are now safe to modify again. Perform recursion:
    quickSort(data, start, left - 1, comp);
    // Handle the middle part - if necessary:
    if(!tied) {
      // TODO: the original publication had a special tie handling here.
      // It shouldn't affect correctness, but probably improves situations
      // with a lot of tied elements.
      quickSort(data, left, right + 1, comp);
    }
    quickSort(data, right + 2, end, comp);
  }
684092
function median(array) {
  var length = array.length;

  if (length === 0) {
    throw new RangeError("Error");
  }

  array.sort(function(a, b) {
    return a - b;
  });

  var middle = Math.floor(length / 2);

  return length % 2 ? array[middle] : (array[middle] + array[middle - 1]) / 2;
}