-
Notifications
You must be signed in to change notification settings - Fork 27
/
mergesort.php
71 lines (60 loc) · 1.01 KB
/
mergesort.php
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
<?php
function merge(&$arr, $l, $m, $r)
{
$n1 = $m - $l + 1;
$n2 = $r - $m;
$L = array();
$R = array();
for ($i = 0; $i < $n1; $i++)
$L[$i] = $arr[$l + $i];
for ($j = 0; $j < $n2; $j++)
$R[$j] = $arr[$m + 1 + $j];
$i = 0;
$j = 0;
$k = $l;
while ($i < $n1 && $j < $n2) {
if ($L[$i] <= $R[$j]) {
$arr[$k] = $L[$i];
$i++;
}
else {
$arr[$k] = $R[$j];
$j++;
}
$k++;
}
while ($i < $n1) {
$arr[$k] = $L[$i];
$i++;
$k++;
}
while ($j < $n2) {
$arr[$k] = $R[$j];
$j++;
$k++;
}
}
function mergeSort(&$arr, $l, $r)
{
if ($l < $r) {
$m = $l + (int)(($r - $l) / 2);
mergeSort($arr, $l, $m);
mergeSort($arr, $m + 1, $r);
merge($arr, $l, $m, $r);
}
}
function printArray($A, $size)
{
for ($i = 0; $i < $size; $i++)
echo $A[$i]." ";
echo "\n";
}
$arr = array(12, 11, 13, 5, 6, 7);
$arr_size = sizeof($arr);
echo "Given array is \n";
printArray($arr, $arr_size);
mergeSort($arr, 0, $arr_size - 1);
echo "\nSorted array is \n";
printArray($arr, $arr_size);
return 0;
?>