Gunnar, Using ALTER SESSION to increase SORT_AREA_SIZE to some obscene number (i.e. several hundred Mb? A Gb?) may help, as long as you are running 8i or below or (if running 9i) the parameter WORKAREA_SIZE_POLICY is set to MANUAL. If WORKAREA_SIZE_POLICY is set to AUTO, then you may have to bump PGA_AGGREGATE_TARGET to something enormous instead...
Are you making use of ALTER INDEX REBUILD to rebuild an index, or are you dropping and then creating? ALTER INDEX REBUILD runs much faster than a CREATE INDEX for two reasons: 1) the REBUILD reads the previous index¹s leaf nodes so there is less I/O since it is smaller and 2) there is no sort operation needed since the previous index¹s leaf entries are already sorted
