Hmm, the query plan looks odd to me. The relationship between estimated and actual suggests that things could be improved, but what's really suprising to me is that the cost estimates of the Sort seems to be based on the preceeding row count estimate (36M) which is way off the actual (0.26M).

Being off by more than two orders of magnitude, I think that the 98% cost estimate for the Sort should be taken with a huge grain of salt.