Thanks for explaining your use-case.

Although the median_* functions don't perform arithmetic on their data, 
they are still conceptually mathematical functions that operate on 
numbers and I'm reluctant to support arbitrary objects with a key 
function without a solid reason. In your example, I think there are 
existing ways to get the result you want:

(1) Use a dict:

data = dict([(1, ['Anna']), (3, ['Paul', 'Henry']), (4, ['Kate'])])
people = data[median_low(data)]

(2) Use a custom numeric type with associated data:

class MyNum(int):
    def __new__(cls, num, data):
        instance = super().__new__(cls, num)
        instance.data = data
        return instance

data = [MyNum(1, ['Anna']), MyNum(3, ['Paul', 'Henry']), 
        MyNum(4, ['Kate'])]

people = median_low(data).data

As for your second example, do you have a use-case for wanting to know 
the position of the median in the original, unsorted list? When would 
that be useful?

One other reason for my reluctance: although median_low and median_high 
guarantee to only return an actual data point, that's a fairly special 
case. There are other order statistics (such as quartiles, quantiles, 
etc) which are conceptually related to median but don't necessarily 
return a data value. Indeed, the regular median() function doesn't 
always do so. I would be reluctant for median() and median_low() to have 
different signatures without an excellent reason.

I'm not completely ruling this out. One thing which might sway me is if 
there are other languages or statistics libraries which offer this 
feature. (I say *might*, not that it definitely will.)