Time complexity of index creation on pre-sorted data

Hi everyone

Does anyone know which sort algorithm is used by the SQL Server index
creation?

Can I generally be sure that a sort of a pre-sorted table (eg. clustering a
heap) can be performed in linear time or shall i still expect O(n log n)
complexity


--
Thomas Kejser

in my experience, time for index creation is pretty much independent of
the original ordering of the table in question.

YMMV. I'd be very curious for someone to  tell me if I'm incorrect.