user
|  |
| --- |
| This page uses content from **Wikipedia**. The original article was at Strand sort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |

Task

Implement the Strand sort.

This is a way of sorting numbers by extracting shorter sequences of already sorted numbers from an unsorted list.
assistant
(formerly Perl 6)

**Works with**: Rakudo version 2018.04.01

```
sub infix:<M> (@x-in, @y-in) {
    my @x = | @x-in;
    my @y = | @y-in;
    flat @x, @y,
        reverse gather while @x and @y {
            take do given @x[*-1] cmp @y[*-1] {
                when More { pop @x }
                when Less { pop @y }
                when Same { pop(@x), pop(@y) }
            }
        }
}

sub strand (@x) {
    my $i = 0;
    my $prev = -Inf;
    gather while $i < @x {
        @x[$i] before $prev ?? $i++ !! take $prev = splice(@x, $i, 1)[0];
    }
}

sub strand_sort (@x is copy) {
    my @out;
    @out M= strand(@x) while @x;
    @out;
}

my @a = (^100).roll(10);
say "Before {@a}";
@a = strand_sort(@a);
say "After  {@a}";

@a = <The quick brown fox jumps over the lazy dog>;
say "Before {@a}";
@a = strand_sort(@a);
say "After  {@a}";

```

Output:

```
Before 1 20 64 72 48 75 96 55 42 74
After  1 20 42 48 55 64 72 74 75 96
Before The quick brown fox jumps over the lazy dog
After  The brown dog fox jumps lazy over quick the
```