# This is a quicksort, using the first line as the pivot, then feeding
# all values less than the pivot to the first forked copy of this script,
# and the values above the pivot to the 2nd forked copy.
#
# Variables:
#    $v : pivot
#    @c : child processes, $c[0] for values less than pivot, and $c[1] for those above
#    $c : count of extra occurrences of pivot, which must be printed with correct count

{
    my $tracing = $ENV{TRACE};

    my $pid = $$;
    my $ppid = getppid();

    sub trace
    {
        printf STDERR "\tPID %8x PPID %8x @_",
                      $pid,
                      $ppid if $tracing;


        print "\n" unless $_[-1]=~/\n/;
    }
}

defined(my $v = <>) or exit;

trace("PIVOT", $v);

# $c is the count of times to print the pivot, while @c is an array of
# filehandles into identical child processes which will handle values below the
# pivot (in $c[0]), and above the pivot (in $c[1]).
my ($c,@c) = 1;
open($_, "|-", "$^X $0") for @c[0,1];

while (<>) {
    if ($_ eq $v) {
        # Need to print pivot multiple times.
        ++$c;
    }
    else {
        if ($_ lt $v) {
            print {$c[1]} $_;

            trace("sending to CHILD 1:", $_);
        }
        else {
            print {$c[0]} $_;

            trace("sending to CHILD 0:", $_);
        }
    }
}

trace("Printing values below pivot",$v);

pop @c; # This closes the left ($c[0]) child, printing all the values less than
        # the pivot, in sorted order.

trace("Printing",$c,"copy(ies) of pivot",$v);
print $v x $c;

trace("Printing values above pivot",$v);

# The right (originally $c[1]) child gets closed and flushed at process exit,
# printing all the values greater than the pivot, in sorted order.