This means you are syncing or did sync contacts direct with the Address Book on your Mac via the iTunes sync process in addition to syncing contacts over the air with your iCloud account.
Do you have Sync Contacts selected under the Info tab for your iPhone sync preferences with iTunes?
Since you should be syncing contacts in the Address Book on your Mac with your iCloud account which in turn is being synced with your iCloud account on your iPhone, the contacts on your Mac should be available in your iCloud address book.
If so, deselect Sync Contacts under the Info tab for your iPhone sync preferences with iTunes followed by selecting Apply if this is currently selected.
On your iPhone go to Settings > iCloud. Turn Contacts off for over the air syncing. Select Delete From My iPhone when prompted.
This should not delete any contacts stored locally on your iPhone - the On My Mac contacts.
Turn Contacts back on for over the air syncing.
You should be provided a merge prompt to merge the contacts stored locally on your iPhone with your iCloud contacts.
Thanks a lot! It seemed to have worked like a charm. And my ultimate goal of having all contacts in one group, namely iCloud, was achieved!
Yes, I did indeed have Sync Contacts selected under the Infor tab for my iPhone, because it was a part of a big process of an attempt of migrating some old contacts from Outlook account to the iCloud. And that was the step that I've stumbled upon so I decided to create a question about that.