-
Notifications
You must be signed in to change notification settings - Fork 0
/
merge-sort.pl
56 lines (46 loc) · 1.22 KB
/
merge-sort.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
##!/usr/bin/perl
use strict;
use warnings;
my @array = (12,11,13,5);
print "Before Sort: [@array]\n";
merge_sort( \@array, 0, $#array );
print "After Sort: [@array]\n";
sub merge_sort {
my ( $ar, $p, $r ) = @_;
if( $p < $r ) {
my $q = int( ($p + $r) / 2);
# divide
merge_sort( $ar, $p, $q );
# divide
merge_sort( $ar, $q + 1 , $r );
# conquer
merge( $ar, $p, $q, $r );
}
}
sub merge {
my ( $ar, $p, $q, $r ) = @_;
# divide into two left and right subarrays
my @left = @$ar[$p .. $q];
my @right = @$ar[$q + 1 .. $r];
# intialize
my $i = my $j = 0;
# now compare both left and half arrays
for my $k ($p .. $r) {
# This check just for sentinals
if(@right and @left) {
#print "@right\n";
if( $left[$i] <= $right[$j] ) {
$ar -> [$k] = shift @left;
}
else {
$ar -> [$k] = shift @right;
}
}
elsif(@left and !@right) {
$ar -> [$k] = shift @left;
}
elsif(!@left and @right) {
$ar -> [$k] = shift @right;
}
}
}