#! perl -slw
use strict;
use Data::Dump qw[ pp ]; $Data::Dump::WIDTH = 1000;

our $N //= 400;
our $G //= 4; my $GSize = int( $N / $G );
our $S //= 1; srand( $S );

my @p = map $_ * $GSize, 0 .. $G-1; #pp \@p;
my @d = map int( rand 1000 ), 1 .. $N;

sub show{ print pp [ @d[ $_ .. $_ + $GSize-1 ] ] for @p; print''; }

splice @d, $_, $GSize, sort{ $a <=> $b } @d[ $_ .. $_ + $GSize-1 ] for @p; show;

## The algorithm starts here; 
## with @d containing $G sorted subpartitions.
## and  @p the start indexes of those sub-partitions
## and  $GSize containing the length of the sub-partitions.
## Note:If the command line args partition the array into $G+1 partitions; 
## eg. -N=100 -G=7 given partitions [0..13][14..27][28..41][42..55][56..69][70..83][84..98][99]
## the last 'extra' partition is ignored. (For now.)

## merge each partition after the first
for my $i ( 1 .. $#p ) {

    ## against all the following partitions starting with the first
    for( my $pA = 0; $pA < $p[ $i ]; ++$pA ) {

        ## $pA indexes to the next element to be merged
        ## if it is less the top element of the partition being merged
        if( $d[ $pA ] > $d[ $p[ $i ] ] ) {
            my $temp = $d[ $pA ];           ## Keep a copy of it
            $d[ $pA ] = $d[ $p[ $i ] ];     ## swap the lower element into place
            my $pB;                         ## external declaration allows $pB to remember where it finished when the next loop terminates

            ## Insertion sort the element being swapped out ($temp) into the right place in the partition being merged with
            for( $pB = $p[ $i ]+1; $pB < ( $p[ $i ]+$GSize ) && $d[ $pB ] < $temp; ++$pB ) { $d[ $pB-1 ] = $d[ $pB ]; };

            ## Put the swapped out element into the gap we opened up
            $d[ --$pB ] = $temp;
        }
    #    show; <STDIN>;
    }
    #show;
}
show;