Wirelessly posted
Since you know your Mac pushes updates to the cloud, I recommend the following.
1. Settings > iCloud. Turn off iCloud contacts on your iPhone.
2. If prompted, delete all contacts from your iPhone (do not select the option to keep them on your phone, or it will create a non-iCloud group).
3. If your contacts are not deleted on the iPhone, manually do so now. Ensure you have zero contacts/groups. Completely remove anything in contacts on your iPhone. (**NOTE** ensure you did step #1. By turning off iCloud deleting your iPhone contacts will not affect the contacts in the Cloud).
4. Log onto iCloud.com from your Mac. Make sure your contacts are still there.
5. On iPhone, Settings > iCloud turn contacts back on. If prompted, select "Merge Contacts" from the cloud to your phone.
This should now sync everything up.
If the thought of deleting all your contacts is unnerving, perform a time machine backup of your Mac before doing any of the above steps so you'll have piece of mind.