If MySQL chooses to build the index(es) on the fly, or wait until all the data is in, then do a sort, etc, to build the index. Note: UNIQUE indexes (I think) have to be built on the fly so that UNIQUEness can be verified. The PRIMARY KEY for InnoDB is stored with the data (or you could state it vice versa), so that MUST be built randomly.
The Index tracks the data (eg AUTO_INCREMENT or timestamp) versus random (GUID, MD5), or somewhere in between (part number, name, friend_id).
Variable #3 (if the index is built on the fly):
The index might fit in cache (key_buffer or innodb_buffer_pool), or it might spill to disk.
Indexes that track the data are efficient, and virtually linear, regardless of the answer to #1.
Random ids are a pain. If the index won't fit in cache, the time to build it will be much worse than linear, regardless of the other variables. (I disagree with Rolando in this case.) A huge InnoDB table with a GUID for the PK is painfully slow to INSERT into -- plan on 100 rows/sec for ordinary disks; maybe 1000 if you have SSDs. LOAD DATA and batched INSERTs won't get you past the slowness of the random storage.
3.53 thru 5.6 -- not much has changed.
Multiple spindles? RAID striping is better in almost any situation than manually assigning this to here and that to there. Manual splitting leads to unbalanced situations -- a table scan is stuck on the data disk; an index-only operation is stuck on the index disk; a lone query first hits the index disk, then the data disk (no overlap); etc.