Another note:

I have a 2nd INSERT, which is somewhat similar:

;INSERT INTO #Grouping (CartID, GroupingNames)

SELECT c.CartID

, STUFF((SELECT '; ' + GroupName FROM CartGroups cg WHERE cg.CartID=c.CartID ORDER BY GroupName FOR XML PATH('')), 1, 2, '') AS GroupingNames

FROM dbo.Cart c

The cost % for this INSERT is 3%, and there is not a sort in the execution plan. It's biggest cost is 87% on the index seek (index on the CartGroup table, CartID and GroupName fields).

I haven't been able to determine why the first insert is so different from this one... I suppose, like Luis said, it's that join...