The threads will be processed in parallel if you start all the threads, and then in a separate loop join with all of them.

I changed the tasks to sleep for variable lengths of time (with rand and Time::HiRes::sleep) to make the output a bit clearer. I also removed the ampersands from subroutine calls like &complete(). One other change is that the way you are doing loops isn't initializing the counter correctly, "for ($i ; $i<5:$i++)" should be "for ($i=0; $i<5; i++)", or even better "for $i (0..4)".

Try the following:

use strict;
use diagnostics;
use threads;

use Time::HiRes;

my @array_of_threads;
my $i = 0;
my $string;

sub first { print "called first\n"; second(); }

sub second {
    ## creating 5 threads
    for ( $i = 0 ; $i < 5 ; $i++ ) {
        $array_of_threads[$i] = threads->new( \&sub1, "$i" );
        print "End of thread " . int( $i + 1 ) . " creation\n";
    }
    ## waiting for all 5 threads to complete
    for ( $i = 0 ; $i < 5 ; $i++ ) {
        print "Waiting for thread $i.\n";
        $array_of_threads[$i]->join();
        print "Joined thread $i.\n";
    }
    complete();
}

sub complete {
    print "The threads have completed execution\n";
}

sub sub1 {
    my $j = $_[0];
    print "Thread $j has entered sub1\n";
    sub2($j);
}

sub sub2 {
    my $k = shift;

    my $n = 10 * rand;
    print "Thread  $k is sleeping for $n seconds.\n";
    Time::HiRes::sleep $n;
    print "Thread $k done.\n";
}

first();
[download]