How to rearrange data in array so that two similar items are not next to each other?

Question

Just want to rearrange the data in array so that similar items are not next to each. The data should not be removed from the array, if it can't be rearranged it can be put at the end of the array. But keeping the original order is necessary.

Example

   1 1 2             =>   1 2 1 
   1 1 1 2 3         =>   1 2 1 3 1
   1 1 2 1 3 3 5 1   =>   1 2 1 3 1 3 5 1
   1 1 1 1 1 1 2     =>   1 2 1 1 1 1 1
   8 2 1 3 7 2 5     =>   rearrange not needed
   8 2 2 2 7 2 5 2   =>   8 2 7 2 5 2 2      // keep the original order

EDIT: Added example to show keeping original order is needed

Answer 1

1. Sort your array

2. Swap elements at small even indexes with their higher antipodal counterparts:

   for ( i=0; i < arr.length/2; i+=2 )
       arr.swap(i,arr.length-1-i);
   

Edit: Okay, we should redefine the antipodal counterparts. Maybe this one is better: mixing the first and third quartile (denoted x, y in illustration), and mixing the second and third quartile (denoted u, v, w). Let the counterparts ascend parallel.

        25%  50%  75%
         |    |    |
    -----[----[----[----
    11122334455667788999
     x y u v w x y u v w  <-- u, v, w, x, y indicate swap positions
    16172839495161738495

Answer 2

Hmm. Bubblesort comes to mind, but with a three-element comparison; that is, if item[x] and item[x + 1] are the same and item[x + 2] is different, swap item[x + 1] and item[x + 2]. Repeat iterating through the list until no swaps occur. Execution order is, of course, horrible, but that should meet your needs.