Если у вас был зарегистрирован и настроен на телефоне Google-аккаунт (а раз качали с плеймаркета, то так оно и есть) и была включена синхронизация, то ваши контакты сохраняются на серверах Google.
Проверить можно зайдя на gmail.com и введя ваши данные.
Слева вверху выбрать Контакты.