Quicksort in Perl using Sedgewick's Medians and what I thought was an original algorithm, but turns out to be called "fat partitions" and was in Version 7 UNIX's qsort

quicksort.pl

#!/usr/bin/env perl

use strict;
use warnings;

use feature qw(say);

########################################################################

package QS;
use Moose;

use POSIX qw(floor);

has 'array_ref' => (
  is => 'rw',
  isa => 'ArrayRef[Int]'
);

has 'pivot' => (
  is => 'rw',
  isa => 'Int'
);


# max of 2 elts
sub max2 {
  my ( $self, $a, $b ) = @_;
  ( $a > $b ) ? $a : $b ;
}

# min of 2 elts
sub min2 {
  my ( $self, $a, $b ) = @_;
  ( $b > $a ) ? $a : $b;
}

# median of 3 elts
sub median3 {
  my ( $self, $triple ) = @_;

  $self->max2( $self->min2( $triple->[0], $triple->[1] ), $triple->[2] );
}

# first middle and last elts of an array
sub first_middle_last {
  my ( $self ) = @_;

  my @array = @{$self->array_ref};
  
  [ $array[0],
    $array[floor($#array / 2)],
    $array[$#array] ];
}

# Meh. Better to find the median pivot at object instantiation
# I copied the "using medians of first, middle and last" from Wikipedia mind.
sub calc_pivot {
  my ( $self ) = @_;

  $self->pivot( $self->median3( $self->first_middle_last() ) );
}

# The algorithm itself. I thought I'd found a new way, but Wikipedia tells
# me that Version 7 UNIX (1979) had qsort implemented like this.
sub quicksort {
  my ( $self ) = @_;

  $self->calc_pivot();

  # Numbers lower than the pivot point
  my @before_pivots = ();
  # Numbers higher than the pivot point
  my @after_pivots = ();
  # Repeated number of pivot points
  my @pivots = ();

  foreach my $val ( @{$self->array_ref} ) {
    if ( $val > $self->pivot ) {
      push @after_pivots, $val;
    } elsif ( $val < $self->pivot ) {
      push @before_pivots, $val;
    } else {
      push @pivots, $val;
    }
  }

  # For the forgetful Perl hacker, $#array > 0 means "two or more elements"
  # @answer is the lower values - ie. before_pivots sorted
  my @answer = ($#before_pivots > 0) ? @{QS->new( 'array_ref' => \@before_pivots )->quicksort()} : @before_pivots;

  # We now push the list of repeated pivots @pivots and,
  # the upper values - ie. after_pivots sorted
  push @answer, @pivots, ($#after_pivots > 0) ? @{QS->new( 'array_ref' => \@after_pivots )->quicksort()} : @after_pivots;

  return \@answer;
}

no Moose;
########################################################################
# Example usage

#package main;
#my @array = ( 19, 5, 7, 3, 38, 98, 4 ,77, 10, 4, 5, 19, 18, 23, 4, 900, 8, 1 );

#use Data::Dumper;
#say Dumper @{QS->new( 'array_ref' => \@array )->quicksort()};
########################################################################