#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;

my @unsortedData = ( 5, 4, 7, 2, 1, 3, 6, 9, 8, 10 );

# show the original data to screen
for( @unsortedData ) {
    print "$_  ";
}
print "\n";

my $sortedData = mergeSort( \@unsortedData );

# show the new data to screen
for( @$sortedData ) {
    print "$_  ";
}
print "\n";

### dereferencing of arrays isnt working in below method

sub mergeSort {
    my ( $data ) = @_;

    if( @$data < 2 ) { return $data; }  # if there is less then two items it's already sorted!!

    use integer;
    #split the array into two parts
    my $middle = @$data / 2;
    print "middle: $middle\n";

    my @leftSide = ();
    print "LeftSide:\n";
    for( my $i = 0; $i < $middle; $i++ ) {
        $leftSide[$i] = @$data[$i];
        print "$leftSide[$i] ";
    }
    print "\n";
    my @rightSide = ();
    print "RightSide:\n";
    for( my $i = $middle; $i < @$data; $i++ ) {
        $rightSide[$i - $middle] = @$data[$i];
        print "$rightSide[$i - $middle] ";
    }
    print "\n";
    mergeSort( \@leftSide );
    mergeSort( \@rightSide );
    merge( \@leftSide, \@rightSide, $data );
    return $data;
}

sub merge {
    my ( $groupA, $groupB, $dataRef ) = @_;
    my $i = 0; my $j = 0; my $k = 0;

    while( $i < @$groupA && $j < @$groupB ) {
        if( $groupA->[$i] <= $groupB->[$j] ) {
            @$dataRef[$k] = $groupA->[$i];
            $i++;
        }
        else {
            @$dataRef[$k] = $groupB->[$j];
            $j++;
        }
        $k++;
    }
    while( $i < @$groupA ) {
        @$dataRef[$k] = $groupA->[$i];
        $i++;
        $k++;
    }
    while( $j < @$groupB ) {
        @$dataRef[$k] = $groupB->[$j];
        $j++;
        $k++;
    }
}