output formatting - How to keep Collect[] result in order?

For example,

Collect[(1 + x + Cos[s] x^2)^3, x]

gives the result

1 + 3 x + 3 x^5 Cos[s]^2 + x^6 Cos[s]^3 + x^2 (3 + 3 Cos[s]) + x^3 (1 + 6 Cos[s]) 
     + x^4 (3 Cos[s] + 3 Cos[s]^2)

Terms of the form $x^n$ are in random order. I would like the result is to be as follows:

 1 + 3 x + x^2 (3 + 3 Cos[s]) + x^3 (1 + 6 Cos[s]) +  
   x^4 (3 Cos[s] + 3 Cos[s]^2) + 3 x^5 Cos[s]^2 + x^6 Cos[s]^3

---

Well, First Thank you very much, Jens! Second, I found there is something wrong with your statement "the HoldForm could be left out". I have tried on my mathematica 8, it turns out that the "HoldForm" is necessary . if "HoldForm" is not there, the order is still random in the output . And I tried to understand this as well as "rule" and "ruledelayed" stuff but can't figure it out. I have tried several input, each confused me. summarized as follows

1. 
   

   Replace[cx, List[x__] -> Plus[x]]

   
   

   will give

   
   

   Sequence[1, 3 x, x^2 (3 + 3 Cos[s]), x^3 (1 + 6 Cos[s]), x^4 (3 Cos[s] + 3 Cos[s]^2), 3 x^5 Cos[s]^2, x^6 Cos[s]^3] 
   

   
   

   But I suppose it should give the Plus result because

   
   

   Replace[cx, List[x__] -> jjj[x]]
   

   
   
   

   gives

   
   

   jjj[1, 3 x, x^2 (3 + 3 Cos[s]), x^3 (1 + 6 Cos[s]),  x^4 (3 Cos[s] + 3 Cos[s]^2), 3 x^5 Cos[s]^2, x^6 Cos[s]^3]
   



2. 
   

   Replace[cx, List[x__] -> HoldForm@Plus[x]] gives the right result

   
   

   1 + 3 x + x^2 (3 + 3 Cos[s]) + x^3 (1 + 6 Cos[s]) +  x^4 (3 Cos[s] + 3 Cos[s]^2) + 3 x^5 Cos[s]^2 + x^6 Cos[s]^3
   



3. 
   

   Replace[cx, List[x__] :> Plus[x]] gives

   
   

   1 + 3 x + 3 x^5 Cos[s]^2 + x^6 Cos[s]^3 + x^2 (3 + 3 Cos[s]) + x^3 (1 + 6 Cos[s]) + x^4 (3 Cos[s] + 3 Cos[s]^2)
   
   

   
   

   Although it gives the right plus result, the order is wrong.

   
   

Answer

Here is an approach that doesn't rely on undocumented features or on low-level box manipulations. We're dealing with a polynomial, so we can simply collect its coefficients and arrange them any way we like as follows:

c0 = Collect[(1 + x + Cos[s] x^2)^3, x];

cx = CoefficientList[c0, x] x^Range[0, Exponent[c0, x]]


(*
==> {1, 3 x, x^2 (3 + 3 Cos[s]), x^3 (1 + 6 Cos[s]), 
 x^4 (3 Cos[s] + 3 Cos[s]^2), 3 x^5 Cos[s]^2, x^6 Cos[s]^3}
*)

Replace[cx, List[x__] :> HoldForm[Plus[x]]]

$1+3 x+x^2 (3+3 \cos (s))+x^3 (1+6 \cos (s))+x^4 \left(3 \cos (s)+3 \cos ^2(s)\right)+3 x^5 \cos ^2(s)+x^6 \cos ^3(s)$

I've just assembled the desired form of the polynomial by creating a list cx of all terms up to the maximum power Exponent[c0, x], and then turning that list into a sum by means of Replace. Here, the HoldForm was put in so that the output now can be arranged in any alternative order by permuting (or, in particular, reversing) the list cx before doing the Replace:

Replace[Reverse@cx, List[x__] :> HoldForm[Plus[x]]]

$x^6 \cos ^3(s)+3 x^5 \cos ^2(s)+x^4 \left(3 \cos (s)+3 \cos ^2(s)\right)+x^3 (1+6 \cos (s))+x^2 (3+3 \cos (s))+3 x+1$

The output is in held form, so if you apply ReleaseHold to it the order will revert back to the first version. The HoldForm could also be exploited to do further cosmetic changes on the expression, such as putting coefficients before the power of x - but you didn't ask for that.

Edit In response to a follow-up question: the Replace command has RuleDelayed (:>) instead of -> in it because the pattern indicated by x__ has to be fed into the Plus only at the time when there is actually a list of terms present. E.g., if you use List[x__] -> Plus[x] then the right-hand side is immediately evaluated to give you x as the result of Plus[x] (assuming that x hasn't been defined globally). And when you then later encounter the Replace statement it will say to feed the pattern inside List into the right-hand side that now has the form x instead of Plus[x]. That will yield something with the head Sequence corresponding to the sequence of arguments inside the given List.