No idea what might constitute a "good" answer. but the following may be of interest:

use strict;
use warnings;

my @original = (1, 2, 3, 4, 5, 6, 7, 8, 3, 5, 6, 3, 8, 1, 7, 8);
my @lists = [shift @original];

for my $value (@original) {
    push @lists, [] if $value < $lists[-1][-1];
    push @{$lists[-1]}, $value;
}

print join (', ', map {"[@$_]"} @lists), "\n";

my @result;

while (@lists) {
    my ($smallest) = sort {$lists[$a][0] <=> $lists[$b][0]} 0 .. $#lis
+ts;
    
    push @result, shift @{$lists[$smallest]};
    @lists = grep{scalar @$_} @lists;
}

print "@result";
[download]

Prints:

[1 2 3 4 5 6 7 8], [3 5 6], [3 8], [1 7 8]
1 1 2 3 3 3 4 5 5 6 6 7 7 8 8 8
[download]

Not that I'm suggesting I'd have produced that in an interview mind you!