How to handle data addition in data grid when data is sorted

The new record should be added based on the sort order selected. Even if that means that the new record won't be visible on the currently selected page. This is to ensure that the data presented it correct and avoids making it look like your application has a potential issue with sorting.

The obvious concern with this approach is that the user might not realise that the record has been added and might attempt to re-do it thus adding duplicate entries.

To circumvent this issue, when a new record is added, regardless of it's visibility on the page you should inform the user with a confirmation message to show that the record has been successfully added.

You could even take this message a step further and warn the user that depending on the sort order of the grid, the new record might not be immediately visible on the current page. Although I expect the "successfully added" message will suffice.