Have you been syncing your contacts in with your Gmail account? When you try to create a new contact it gives you for option. Phone, sim, Samsung account and Google account. If you have been saving in your Google account or ever merged contacts with your Google account, you can retrieve them by signing in your Google account. If you haven't done it at past, please take it as a valuable lesson and always save and sync your contacts with your Google account.
Sent from my GT-I9100 using Android Central Forums