my $index = 0;
++$index while $k >= $array[ $index ];
splice @array, $index, 0, $k;