The exercise is a bit weird. The problem statement says "find the record" but all the answers are about printing the median age.

So answer to the question posed? None of the above. One can make a simplifying observation that ages are all < 255. I'd then use a radix sort.

   from random import randint
   from time import time

   x = [(randint(20,80), "John Smith")  for x in range(2_300_000)]

   start = time.time()
   ages = [0] * 256
   for entry in x:
       ages[entry] += 1
   for age, count in enumerate(ages):
       total += count
       if total >= 2_300_000//2:
           print(age)
           break
   print(time.time() - start)

This is ~1.6x faster than the variant that uses sort with a custom key that someone else posted. If you simplify it into an array of numbers, it's still 5-10% faster on my machine than sort (i.e. comparing pure native code running sort vs running radix sort in interpreted Python).

If you converted this to native code I'm sure this would be over an order of magnitude faster, both because O(N) is faster than O(n log n) and because you're doing a linear scan through the records (just jumping randomly around within a 255 byte array which can be 1 cache line on some CPUs). Indeed, when I compare this in native code [1], on my machine it's 3ms for radix sort processing of 2.3M records vs 77ms (~25x faster). When run with -O0, it's 24ms vs 724ms (~30x faster).

If I needed to find the actual record for the median employee(s) (there can be more than one obviously), I'd just scan over the data linearly a second time which should STILL be faster [2] (in the benchmark it's still 7x faster than comparison sort).

[1] https://quick-bench.com/q/Bra8T5nv9nFzgUUUKxjVLNCie6I [2] https://quick-bench.com/q/CN0WBMpyICM2ZwnwgQadBX3cPj4