Code Golf: Mix the nuts so that none of the same kind are touching Input:

Input is a randomized array of nuts (in your language), the possible nuts follow. Your program must have a way of representing each kind of nut, such as an integer code. Program must be able to handle any size array of any configuration of nuts.

Possible Nuts:

Kola nut
Macadamia
Mamoncillo
Maya nut
Mongongo
Oak acorns
Ogbono nut
Paradise nut
Pili nut
Pistachio
Walnut


Output:

Output must be the array sorted in such a fashion that there are no adjacent nuts of the
same kind. If this is impossible, the output should be an empty array.

Example Input (simplified):

["walnut", "walnut", "pistachio"]


Example Output:

["walnut", "pistachio", "walnut"]


Solutions may not simply shuffle the array until it becomes unique by chance. The sort employed must be a deterministic one
GolfScript, 42 41 37 38 characters
~.`{\`{=}+%1-,}+$.,)2//zip[]*.2&lt;..&amp;=*p

The code expects input on STDIN and prints result to STDOUT, e.g.:
&gt; [&quot;walnut&quot; &quot;walnut&quot; &quot;walnut&quot; &quot;macadamia&quot; &quot;pistachio&quot;]
[&quot;walnut&quot; &quot;macadamia&quot; &quot;walnut&quot; &quot;pistachio&quot; &quot;walnut&quot;]

&gt; [&quot;walnut&quot; &quot;walnut&quot; &quot;walnut&quot; &quot;macadamia&quot; &quot;walnut&quot;]
[]

The script became longer than expected but I suppose there is room for improvement.
Edit: The case of a list with a single item costs me 1 character (the best comparison I could come up with is the same as Peter's).