Not sure what carrier your on, but I know Verizon doesn't save contacts to a SIM and never have to my knowledge. They have also offered the ability to back them up for free since the flip phone days but most never bothered with the free service.
Your carrier might have a back up, they also should have been saved to your Google Account unless you chose to save them to local storage instead.