> and is already sorted by the db, Right, if it's already sorted just taking the midpoint is the obviously correct algorithm (and O(1) time/space). It's only

> and is already sorted by the db, Right, if it's already sorted just taking the midpoint is the obviously correct algorithm (and O(1) time/space). It's only in the unsorted cases where with giant lists you should start thinking about alternatives. If I'm working with gigabytes of photon counts (each element representing the number photons detected in a time interval) I don't want to sort my gigabyte long list before getting the median - sorting would destroy the very important structure of the data so I'd just have to throw away the copy afterwards. This is referencing some code I worked on a long time ago. I'm not sure I had to calculate a median specifically, but similar enough statistics. It's a simple function, but not a one size fits all algorithm.