You've not provided sufficient details for us to give you detailed guidance on exactly how to approach this, but I can provide you with some information that may help guide you. Each object has it's own sharing table. For Contact, there will be a ContactShare object (See the Object Reference). A Share object exists for every Standard object that supports sharing and for all custom objects.
When new shares are created or existing ones removed, the sharing table is recalculated. This can be a time consuming process when there's a large database and it can cause long running operations. That's when you may want to enable "Defer Sharing Calculations". See A Guide to Sharing Architecture.
Defer Sharing Calculations
If you have an object that utilizes sharing and has a large volume of records (such as more than two million accounts), and you need to make a bulk change (such as a quarterly realignment requiring a hierarchy change), then there is a feature that can be enabled by Salesforce Support to defer automatic sharing calculations. Natively, every individual change to the role hierarchy, territory hierarchy, groups, sharing rules, user roles, team membership, or ownership of records can initiate automatic sharing calculations. When a bulk change is made, it causes a number of automatic sharing recalculations to begin. By suspending these temporarily, you are able to make the change and then have sharing calculations happen all at once. This is typically a more efficient and better performing method to bulk changes.
I would also recommend you look at Record-Level Access: Under the Hood to understand the concepts involved with sharing that affect sharing tables.
I'm confident you already understand the need for load order, or you wouldn't have posted this question. For those that may not, there's an excellent short video series on You Tube covering Data Import.