Thanks for the replays.

--Here is the answers to the follow up questions:

1) I have to create this Index online since it is huge and I cannot afford such a long down time.

2) MAXDOP was set to 10 at first and showed no significant improvement in speed. I believe at the end the create index still happens on 1 processor anyways.

3) Also SORT_IN_TEMPDB = OFF or ON still didn't matter as SQL always seemed to use up all of the tempdb.

4) This table is already partitioned by date and currently has 570 partitions.