Insertionsort in perl

Insertion sort is significantly slower than the other sorts, but I think I could improve this by doing an O(log n) insert, whereas here I have a linear insert.

#!perl



use strict;



my ($list_size, $max_num, @numbers, $start_time);



#Generate a large number of random integers

$list_size = 10000;

$max_num = 1000;

@numbers = ();

for(1..$list_size) {

  push(@numbers, int(rand($max_num)));

}



#Print out the number array, then sort it, then print it out again in sorted order

#print "\n\n@numbers";

$start_time = time;

@numbers = @{insertionsort(\@numbers)};

#print "\n\n@numbers";

print "INSERTIONSORT sorted $list_size integers between 1 and $max_num in " . (time - $start_time) . " seconds\n";



#Insertion sort is how humans often sort a deck of cards

#Start with a stack of unsorted numbers, pop each number in turn

#And insert it into a second sorted stack at the proper place

sub insertionsort {

  my ($numbers, @sorted, $found);

  ($numbers) = @_;

  my @sorted = ();

 

  for(my $i = 0; $i <= $#{$numbers}; $i++) {

    $found = 0;

    for(my $j = 0; $j <= $#sorted; $j++) {

      if( $numbers->[$i] < $sorted[$j] ) {

        splice @sorted, $j, 0, $numbers->[$i];

        $found = 1;

        last;

      }

    }

  unless ($found) { push @sorted, $numbers->[$i]; }

  }

 

  return \@sorted;

}