Task — Wiggle sort

You are given a list of integers, @list. Write a script to perform Wiggle Sort on the given list. In a wiggle sorted list:

list[0] < list[1] > list[2] < list[3] …

Examples

Example 1
Input: @list = (1, 5, 1, 1, 6, 4)
Output:        (1, 6, 1, 5, 1, 4)

Example 2
Input: @list = (1, 3, 2, 2, 3, 1)
Output:        (2, 3, 1, 3, 1, 2)

Analysis

If the list has an even number of elements then the solution is reasonably straightforward: sort @list and interlace the first half with the second, eg:

1, 2, 3, 4, 5, 6 => 1, 4, 2, 5, 3, 6

It won't work, and there is no solution, for a list where more than half of the elements are equal, eg:

1, 1, 1, 1, 2, 3

If the list has an odd number of elements my solution sorts the list, sets aside the last element, and as above interleaves the two halves of the remaining list. If the last element of the resulting list is greater than the last element of the interleaved list, then it can simply be added to the end:

1, 2, 3, 4, 5, 6, 7 => 1, 4, 2, 5, 3, 6, 7

The problem arises if it is equal to the last element:

1, 2, 3, 4, 5, 6, 6 => 1, 4, 2, 5, 3, 6 + ?? 6

My solution is to look successively at the third last, fifth last and so on elements until one is found that is less than the orphaned element, to put the orphaned element in its place and add the displaced element to the end:

1, 2, 3, 4, 5, 6, 6 => 1, 4, 2, 5, 3, 6 => 
                                       1, 4, 2, 6, 3, 5

If no such swap can be done then the sort is impossible. It will happen, again, only if more than half the elements in @list are equal.

Try it 

Try running the script with any input:

Your @list =

example: 1, 3, 5, 7, 8, 6, 4, 2

⤡

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2022-12-26
use utf8;     # Week 197 - task 2 - Wiggle sort
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

wiggle_sort(1, 5, 1, 1, 6, 4);
wiggle_sort(1, 6, 4);
wiggle_sort(1, 3, 2, 2, 3, 1);
wiggle_sort(1, 2, 3, 4, 9, 9, 9);
wiggle_sort(1, 4, 2, 4, 3, 4, 5, 4, 6, 4, 7, 4, 8);

my @list;
$list[$_] = int(rand(5)) for 0 .. 20;
wiggle_sort(@list);

sub wiggle_sort {
    
    my (@list, $i, $j, $stop, @sorted);
    
    @list = @_;
    say qq[\nInput:  \@list = (] . join(', ', @list) . ')';
    
    # initialise
    @list = sort { $a + 0 <=> $b + 0 } @list;
    $stop = int(@list / 2) - 1;
    
    # alternate 1st and 2nd halves of sorted list
    for $i (0 .. $stop) {
        push @sorted, $list[$i];
        push @sorted, $list[$i + $stop + 1];
        
        # list can't be wiggle-sorted
        if ($sorted[-1] == $sorted[-2] or
            ($i >= 2 and $sorted[-2] == $sorted[-3])) {
            say qq[Output:          not possible];
            return;
        }
    }
    
    # deal with last number in odd-numbered list
    if (@list & 1) {
        
        # if the last number in @list is the same as the
        # last one in @sorted (see blog)
        for ($i = @sorted - 1; $i >= 0; $i -= 2) {
            if ($list[-1] > $sorted[$i]) {
                push @sorted, $sorted[$i];
                $sorted[$i] = $list[-1];
                last;
            }
            
            # list can't be wiggle-sorted
            if ($i == 1) {
                say qq[Output:          not possible];
                return;
            }
        }
    }

    say qq[Output:         (] . join(', ', @sorted) . ')';
}

Output

Input:  @list = (1, 5, 1, 1, 6, 4)
Output:         (1, 4, 1, 5, 1, 6)

Input:  @list = (1, 6, 4)
Output:         (1, 6, 4)

Input:  @list = (1, 3, 2, 2, 3, 1)
Output:         (1, 2, 1, 3, 2, 3)

Input:  @list = (1, 2, 3, 4, 9, 9, 9)
Output:         (1, 9, 2, 9, 3, 9, 4)

Input:  @list = (7, 3, 4, 8, 9, 1, 2, 5, 2, 9, 6, 3, 4)
Output:         (1, 4, 2, 5, 2, 6, 3, 7, 3, 9, 4, 9, 8)

Input:  @list = (1, 1, 1, 9, 9, 9, 9)
Output:          not possible

Input:  @list = (10, 6, 7, 2, 2, 1, 4, 7, 5, 9, 4, 11,
14, 6, 13, 3, 8, 14, 2, 8, 5, 13, 6, 1, 4, 0, 5, 7, 0, 3,
3, 2, 11, 2, 4, 3, 1, 3, 1, 3, 2, 0, 8, 7, 10, 9, 4, 8,
6, 3, 5, 8, 5, 5, 6, 7, 9, 8, 13, 4, 5, 11, 7, 8, 6, 1,
14, 8, 1, 6, 3, 13, 9, 8, 2, 12, 2, 14, 11, 2, 8, 1, 4,
7, 1, 8, 6, 10, 12, 4, 13, 5, 1, 13, 9, 7, 3, 6, 7, 2, 7)
Output:         (0, 6, 0, 6, 0, 6, 1, 6, 1, 6, 1, 6, 1,
7, 1, 7, 1, 7, 1, 7, 1, 7, 1, 7, 2, 7, 2, 7, 2, 7, 2,
7, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 3, 8, 3, 8, 3, 8,
3, 8, 3, 8, 3, 9, 3, 9, 3, 9, 3, 9, 4, 9, 4, 10, 4, 10,
4, 10, 4, 11, 4, 11, 4, 11, 4, 11, 5, 12, 5, 12, 5, 13,
5, 13, 5, 13, 5, 13, 5, 13, 5, 14, 6, 14, 6, 14, 6, 14,
13)