Performance tuning a cascading delete with many foreign keys

Question

I have a delete query that is taking a long time. Looking at the execution plan, I see that most of the estimated cost in the delete query is in a section of the data model that had a lot of data (say, 400k rows) which seemed fine, but I don't understand one thing.

Stripped down view of data model:

table ParentObject 
      int parentObjectId (PK)

table Child
      int childId (PK)
      int parentId (FK)
      <stuff>

table GrandChild
      int grandChildId (PK)
      int childId (FK)
      <more stuff>

Where a parent object might have 200,000 Children, and a Child has 2 or so GrandChildren. I am interested in tuning the performance of:

DELETE FROM ParentObject WHERE parentObjectId = %d;

On Grandchild, there is an extra nonclustered index on (childId, + two other columns) as well as the primary key index. On child there is an extra nonclustered unique index (parentId, + two other columns).

The thing that I saw in the query plan is that while deleting the Grandchild objects, there were two expensive sorting operations mixed in with the deletions, and I don't understand why they are there.

What should I be looking at to help this delete operation go faster? Does it need to sort? Would it help if I denormalized the ids and added a parent Id to the grandchild table? Did I build my index stupidly?

The full execution plan is here.