C:\test>inplaceMerge -N=12 -G=3
Starting point:
 pA=0                p[i]=4 
[231, 584, 675, 787] [165, 177, 714, 838] [451, 456, 714, 887]     temp = d[pA]:231, d[pA] = d[p[i]]:165, d[pB-1] = d[pB]:177, d[--pB] = temp:231
      pA=1           p[i]=4
[165, 584, 675, 787] [177, 231, 714, 838] [451, 456, 714, 887]     temp = d[pA]:584, d[pA] = d[p[i]]:177, d[pB-1] = d[pB]:231, d[--pB] = temp:584
           pA=2      p[i]=4
[165, 177, 675, 787] [231, 584, 714, 838] [451, 456, 714, 887]     temp = d[pA]:675, d[pA] = d[p[i]]:231, d[pB-1] = d[pB]:584, d[--pB] = temp:675
                pA=3 p[i]=4
[165, 177, 231, 787] [584, 675, 714, 838] [451, 456, 714, 887]     temp = d[pA]:787, d[pA] = d[p[i]]:584, d[pB-1] = d[pB]:675,  d[pB-1] = d[pB]:714, d[--pB] = temp:787

 pA=0                                     p[i]=8
[165, 177, 231, 584] [675, 714, 787, 838] [451, 456, 714, 887] 
      pA=1                                p[i]=8
[165, 177, 231, 584] [675, 714, 787, 838] [451, 456, 714, 887]
           pA=2                           p[i]=8
[165, 177, 231, 584] [675, 714, 787, 838] [451, 456, 714, 887]
                pA=3                      p[i]=8
                
[165, 177, 231, 584] [675, 714, 787, 838] [451, 456, 714, 887]     temp = d[pA]:548, d[pA] = d[p[i]]:451, d[pB-1] = d[pB]:456, d[--pB] = temp:458
                      pA=4                p[i]=8
[165, 177, 231, 451] [675, 714, 787, 838] [456, 584, 714, 887]     temp = d[pA]:675, d[pA] = d[p[i]]:456, d[pB-1] = d[pB]:584, d[--pB] = temp:675
                           pA=5           p[i]=8
[165, 177, 231, 451] [456, 714, 787, 838] [584, 675, 714, 887]     temp = d[pA]:714, d[pA] = d[p[i]]:584, d[pB-1] = d[pB]:675, d[--pB] = temp:714
                                pA=6      p[i]=8
[165, 177, 231, 451] [456, 584, 787, 838] [675, 714, 714, 887]     temp = d[pA]:787, d[pA] = d[p[i]]:675, d[pB-1] = d[pB]:714, d[pB-1] = d[pB]:714, d[--pB] = temp:787
                                     pA=7 p[i]=8
[165, 177, 231, 451] [456, 584, 675, 838] [714, 714, 787, 887]     temp = d[pA]:838, d[pA] = d[p[i]]:714, d[pB-1] = d[pB]:714, d[pB-1] = d[pB]:787, d[--pB] = temp:838


##</code><code>##

#! 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;