Insertion sort using arrays

#!/usr/bin/perl -w
for ($size=100; $size<10000; $size *= 2) {

# Fill an array with $size random values

for ($i=0; $i<$size; $i++) {
  $x[$i] = rand 10;
}

$start = times();

# move first element to sorted array
$isorted[0] = $x[0];

for ($next_el=1; $next_el < $size; $next_el++) {
  
  # move next element to sorted array
  $isorted[$next_el] = $x[$next_el];
  
  # Swap new element down to its correct position
  $swap_ind = $next_el;
  while ( ($swap_ind>0) && 
       ($isorted[$swap_ind-1] > $isorted[$swap_ind]) ) {
	   
    $tmp = $isorted[$swap_ind-1];
    $isorted[$swap_ind-1] = $isorted[$swap_ind];
    $isorted[$swap_ind] = $tmp;
    $swap_ind--;
  }
}

$end = times();

# double-check that algorithm was implemented correctly
$sorted = "true";
foreach ( 0..($size-2) ) {
  if ($isorted[$_] > $isorted[$_ + 1]) {
    $sorted = "false";
  }
}
if ($sorted == "false") {
  print "Sort is incorrect\n";
}

  printf "%g,%g\n", $size, $end - $start;
}

Typical output

100,0.01
200,0.03
400,0.15
800,0.43
1600,1.64
3200,6.39
6400,25.35

Insertion sort using list and stack operations

#!/usr/bin/perl -w
for ($size=100; $size<=10000; $size *= 2) {

# Fill an array with $size random values

@x = rand 10;
foreach ( 1..($size-1) ) {
  push @x, rand 10;
}

$start = times();

# move first element to sorted array
@isorted = shift @x;

foreach ( 1..($size-1) ) {
  # get the next element to be inserted
  $next_x = shift @x;

  # scan through the sorted list to find the
  # location for the new element, shifting
  # elements to a temporary list one by one
  $temp = pop @isorted;
  @temp_sorted = ();
  while ( @isorted && ($temp > $next_x)) {
    unshift @temp_sorted, $temp;
    $temp = pop @isorted;
  }

  # when the location is found, insert the new
  # element and reinsert the last item examined
  if ($temp > $next_x) {
    push @isorted, $next_x;
    push @isorted, $temp;
  } else {
    push @isorted, $temp;
    push @isorted, $next_x;
  }

  # shift the elements from the temporary list
  # back to the sorted list
  while ( @temp_sorted ) {
    $temp = shift @temp_sorted;
    push @isorted, $temp;
  }
}

$end = times();

# double-check that algorithm was implemented correctly
$sorted = "true";
foreach ( 0..($size-2) ) {
  if ($isorted[$_] > $isorted[$_ + 1]) {
    $sorted = "false";
  }
}
if ($sorted eq "false") {
  print "Sort is incorrect\n";
}

  printf "%g,%g\n", $size, $end - $start;
}

Typical output

100,0.01
200,0.03
400,0.14
800,0.4
1600,1.52
3200,6.07
6400,24.44