How to indicate insertion of a new record into table with pagination

I'm looking for a way to indicate successful addition of new record to table.

I have two main elements on my page - a form used to add new records and, below, a table displaying all the existing records. The table is sorted alphabetically and paginated.

When a user adds a new record I need to indicate that it was saved and entered into the table but if the new record's sort order in the table would not place it in view, how should I indicate that the entry was successful? And should I refresh the table to show the range of results that contain the new entry?