#!/usr/bin/perl
use Time::HiRes qw(time);



# Return a list of random numbers
#  $numbers = random_numbers($how_many, $max_value)
sub random_numbers {
  my ($n, $max_number) = @_;
  my $numbers = [];
  for (my $i=0; $i<$n; $i++){
    push @$numbers, int(rand($max_number));
  }
  return $numbers;
}


# Sort a list of numbers using the radix algorithm.
#  This is slightly faster if the rough size largest number of the list is given
#  by specifying its number of digits base 10 (eg "3" for "999").
#  You can also specify how many numbers from the start 
#  and end of the list to print for debugging.
#    $sorted_list_ref = radix_sort($list_ref)
#  or
#    $sorted_list_ref = radix_sort($list_ref, $max_digits)
#  or
#    $sorted_list_ref = radix_sort($list_ref, $max_digits, $show_debug_numbers)
sub radix_sort {
  my $numbers    = shift;
  my $max_digits = shift || 1e6; # 10**(1e6) is effectively infinity
  my $show       = shift || 0;   # how many to show for debugging; 0 => no debug
  my $digit = 0;
  my $continue = 1;
  while ($continue and $digit < $max_digits){
    print " Starting sort on digit $digit .. \n" if $show;
    my $sorting_list;
    $sorting_list->[$_] = [] for 0..9;
    for my $number (@$numbers){
      my $key = nth_digit($number, $digit);
      $continue = 1 if $key > 0;             # stop if all nth_digit's are zero.
      push @{$sorting_list->[$key]}, $number;
    }
    $numbers = [];
    push @$numbers, @{$sorting_list->[$_]} for 0..9;

    if ($show){
      print " .. done digit $digit\n";
      printf(" %12d  %12d \n", $_, $numbers->[$_])
        for (0 .. ($show-1), $n-($show+1) .. $n-1);
    }

    $digit++;
  }
  return $numbers;
}
