In order to execute parallel queries as efficiently as possible, Parallel LINQ (PLINQ) treats ordering as optional. By default, PLINQ considers sequences to be unordered, unless the user explicitly opts into maintaining ordering using either the AsOrdered or the OrderBy operator.

Roy Patrick Tan wrote a detailed article that explains the precise ordering guarantees made by PLINQ for various types of queries: PLINQ’s Ordering Model

(This paper and many more are available through the Parallel Computing Developer Center on MSDN at http://msdn.microsoft.com/en-us/concurrency/ee851578.aspx.)