With the OP's spec of 3.5 million items, if there are no dups your method will have to do...

3,500,000 + 3,499,999 + 3,499,998 + ... + 1 = 3,062,501,750,000

...comparisons. Three trillion string comparisons is probably not the quickest way to go.

On a tangent, one of the problems with using a sorted index array (instead of sorting a mirror array) is that you end up needing to sort twice; first when you create the sorted index, then after removing the dups you have to sort the index array back to the original order. So I think sorting a mirror array and using a boolean lookup array might be the fastest way to go, especially if the routines get highly optimized. (My posted solution isn't optimized at all.)