It appears sort has a --stable flag for order preservation. I actually thought sort was stable by default already, but now I know.