# Nicholas Rinard Keene's Little Bit

## Saturday, September 12, 2009

### 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;
}
```