Innodb can indexes built by sort since Innodb Plugin for MySQL 5.1 which is a lot faster than building them through insertion, especially for tables much larger than memory and large uncorrelated indexes you might be looking at 10x difference or more. Yet for some reason Innodb team has chosen to use very small (just 1MB) and hard coded buffer for this operation, which means almost any such index build operation has to use excessive sort merge passes significantly slowing down index built process.
Mark Callaghan and Facebook Team has fixed this in their tree back in early 2011 adding innodb_merge_sort_block_size variable and I was thinking this small patch will be merged to MySQL 5.5 promptly, yet it has not happen to date.

Here is example of gains you can expect (courtesy of Alexey Kopytov), using 1Mil rows Sysbench table.

Buffer Length   |  alter table sbtest add key(c)
1MB                      34 sec
8MB                      26 sec
100MB                    21 sec
128MB                    17 sec
REBUILD                  37 sec

REBUILD in this table is using “fast_index_creation=0″ which allows to disable fast index creation in Percona Server and force complete table to be rebuilt instead.

Looking at this data we can see even for such small table there is possible to improve index creation time 2x by using large buffer. Also we can see we can substantially improve performance even
increasing it from 1MB to 8MB, which might be sensible as default as even small systems should be able to allocate 8MB to do alter table.

You may be wondering why in this case table rebuild is so close in performance to building index by sort with small buffer – this comes from building index on long character field with very short length, Innodb would use fixed size records for sort space which results in a lot more work done than you would otherwise need. Having some optimization to better deal with this case also would be nice. The table also was fitting in buffer pool completely in this case which means table rebuild could have done fast too.

Results are from Percona Server 5.5.24