#! perl
use strict;
use warnings FATAL => 'all';
use experimental 'smartmatch';
use List::MoreUtils 'zip';
use Test::More tests => 7;

while (<DATA>)
{
    my ($left, $right) = split /->/;
    my  @array         = split ' ', $left;
    my  @expected      = split ' ', $right;
    my  $aa            = unsort(\@array);
    ok( @$aa ~~ @expected );
}

sub unsort
{
    my $aref  = shift;
       @$aref = sort { $a <=> $b    } @$aref;
    my %nums  = map  { $_  => undef } @$aref;

    return $aref if scalar keys %nums == 1;

    my $half = int(($#$aref + 2) / 2);
  
    if (scalar keys %nums == 2)
    {
        if ($aref->[$half - 1] == $aref->[$#$aref])
        {
            @$aref = (@$aref[$half .. $#$aref  ],
                      @$aref[0     .. $half - 1]);
            @$aref[$half - 1, $#$aref] = @$aref[$#$aref, $half - 1];
        }
    }
    else
    {
        for my $i (0 .. $half - 1)
        {
            last if $i + $half > $#$aref;

            if ($aref->[$i] == $aref->[$i + $half - 1])
            {
                @$aref = (@$aref[$i .. $#$aref], @$aref[0 .. $i - 1]);
            }
        }
    }

    my  @first  = @$aref[0     .. $half - 1];
    my  @second = @$aref[$half .. $#$aref  ]; 
        @$aref  = zip @first, @second; 
    pop @$aref unless defined $aref->[-1];

    return $aref;
}

__DATA__
0 0 1             -> 0 1 0
0 1 1             -> 1 0 1
1 2 3 3 2 2 1     -> 1 2 1 3 2 3 2
3 2 1 2 1 3 2     -> 1 2 1 3 2 3 2
1 3 3 3 3 1 1     -> 3 1 3 1 3 1 3
1 1 1 2 3         -> 1 2 1 3 1
1 1 1 2 3 3 2 2 1 -> 1 2 1 2 1 3 1 3 2
[download]