Pretty sure the section in the `ps` man page called OBSOLETE SORT KEYS indicates that even the `ps` on very old redhat machines could do this out of box... see the field `start_time`.
Failing that, consider the `etimes` field (seconds since process was started) used in conjunction with the -o feature (control output format) so you can put `etimes` up front then simple pipe the output to `sort`.
Those things being said, the situation you describe is indeed hairy. `ps` output was designed for human consumption, that's why the process age field format varies (1w vs 10:15) and that's presumably why you wanted to bring python into the mix!
...You might have had an easier time looking in /proc...
Indeed, this looks promising:
cat /proc/[0-9]*/stat|sort -n|less -S
EDIT: hm, I don't know how old /proc is!
EDIT #2: But try doing ANY of this on an ancient Windows machine! The "peer" of your old Redhat machine would be what, a Win2k3 machine, or a Win2k? How old is PowerShell? :)