Heapsort

sub heap_sort ( @list ) {
    for ( 0 ..^ +@list div 2 ).reverse -> $start {
        _sift_down $start, @list.end, @list;
    }

    for ( 1 ..^ +@list ).reverse -> $end {
        @list[ 0, $end ] .= reverse;
        _sift_down 0, $end-1, @list;
    }
}

sub _sift_down ( $start, $end, @list ) {
    my $root = $start;
    while ( my $child = $root * 2 + 1 ) <= $end {
        $child++ if $child + 1 <= $end and [<] @list[ $child, $child+1 ];
        return if @list[$root] >= @list[$child];
        @list[ $root, $child ] .= reverse;
        $root = $child;
    }
}

my @data = 6, 7, 2, 1, 8, 9, 5, 3, 4;
say 'Input  = ' ~ @data;
@data.&heap_sort;
say 'Output = ' ~ @data;

Output:

Input  = 6 7 2 1 8 9 5 3 4
Output = 1 2 3 4 5 6 7 8 9

Last updated