Perl mergesort - array reference

Question

I was trying to implement merge-sort in Perl, I am quite new to Perl and I know I am doing something wrong with the array references. The arrays end up holding the same value after the process is done. Please help cause I don't see where I am going wrong.

The Corrected Code:

use strict;
use warnings;
my ( @aref, @auxref ) = ();
my ( $hi, $lo, $i, $j, $k, $n ) = 0;

@aref = ( 5, 7, 6, 3, 4, 1, 8, 9, 4 );
$n = @aref;

mergeSort( \@aref, \@auxref, 0, $n - 1 );

print "@auxref\n";
print "@aref\n";

sub mergeSort {

    my ($aref)   = $_[0];
    my ($auxref) = $_[1];
    my $lo       = $_[2];
    my $hi       = $_[3];

    if ( $hi <= $lo ) { return; }
    my $mid = 0;
    $mid = int( $lo + ( $hi - $lo ) / 2 );
    mergeSort( $aref, $auxref, $lo,      $mid );
    mergeSort( $aref, $auxref, $mid + 1, $hi );

    merge( $aref, $auxref, $lo, $mid, $hi );

}

sub merge {

    my ($aref)   = $_[0];
    my ($auxref) = $_[1];
    my $lo       = $_[2];
    my $mid      = $_[3];
    my $hi       = $_[4];

    for ( $i = $lo ; $i <= $hi ; $i++ ) {
        $auxref->[$i] = $aref->[$i];
    }

    $i = $lo;
    $j = $mid + 1;

    for ( $k = $lo ; $k <= $hi ; $k++ ) {
        if ( $i > $mid ) {
            $aref->[$k] = $auxref->[$j];
            $j++;
        }
        elsif ( $j > $hi ) {
            $aref->[$k] = $auxref->[$i];
            $i++;
        }
        elsif ( $auxref->[$i] <= $auxref->[$j] ) {
            $aref->[$k] = $auxref->[$i];
            $i++;
        }
        else {
            $aref->[$k] = $auxref->[$j];
            $j++;
        }
    }
}

Answer 1

In sub merge, you have two array refs: $auxref and $aref.

And you're accessing the array elements as though they were ordinary arrays (i.e. $aref[0]) but as they are array references, you need to dereference with an arrow first: $aref->[0].

Adding use strict; and use warnings; to the top of your script should have weeded out these errors though?

Arrays

my @arr = (1, 2, 3, 4);
$arr[0] = 5;
push @arr, 6;
# @arr = (5, 2, 3, 4, 6)

Array References

my $arr = [1,2,3];
$arr->[0] = 5;
push @$arr, 6;
# $arr = [5, 2, 3, 4, 6];

2D arrays of array references

my @arr = ([1, 2], [3, 4]);
print $arr[0][1]; # identical to $arr[0]->[1];
push @{$arr[1]}, 5;
# @arr = ([1, 2], [3, 4, 5]);

2D arrayref of array references

my $arr = [[1, 2], [3, 4]];
print $arr->[0][1]; # identical to $arr->[0]->[1];
push @{$arr->[1]}, 5;
# $arr = [[1, 2], [3, 4, 5]];

2D Array of arrays

...can't exist because an array can only hold scalars

my @arr = ((1, 2), (3, 4));
# @arr = (1, 2, 3, 4);

Answer 2

The following is a version of merge sort that doesn't rely on references at all. It almost certainly isn't as memory efficient as some of the original merge sort algorithms were intended, but it gets the job done.

use strict;
use warnings;

my @array = ( 5, 7, 6, 3, 4, 1, 8, 9, 4 );

my @sorted = mergeSort(@array);

print "@sorted\n";

sub mergeSort {
    my @array = @_;

    if (@array > 1) {
        my $mid = int(@array / 2);

        my @lowArray = mergeSort(@array[0..$mid-1]);
        my @highArray = mergeSort(@array[$mid..$#array]);

        # Merge the two halves      
        my @newArray = ();
        while (@lowArray && @highArray) {
            if ($lowArray[0] < $highArray[0]) {
                push @newArray, shift @lowArray;
            } else {
                push @newArray, shift @highArray;
            }
        }

        # Either the low or high array will be empty at this point,
        # so no need to compare for the remainder.
        return (@newArray, @lowArray, @highArray);

    } else {
        return @array;
    }
}