See if your phone is synced with your computer where the contacts are synced via the PC... Then see in iCloud settings the contacts is "on"
Try turning it off..(take a backup of your device before that) .. Select delete from my phone... Then turn it back on.. If all ur contacts are back it means it's stored on iCloud.. If not then.. Probably I don't have an answer to that