-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathMergeSort.php
More file actions
44 lines (40 loc) · 1.11 KB
/
Copy pathMergeSort.php
File metadata and controls
44 lines (40 loc) · 1.11 KB
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
<?php
/**
* @author tiger
*/
namespace Algorithm\Sorting;
class MergeSort
{
public function sort(array $ary)
{
if (count($ary) < 2) {
return $ary;
} elseif (count($ary) > 2) {
$middle = (int)floor(count($ary) / 2);
$sortedAry1 = $this->sort(array_slice($ary, 0, $middle));
$sortedAry2 = $this->sort(array_slice($ary, $middle));
} else /* count($ary) is 2 */ {
return $ary[0] <= $ary[1] ? $ary : [$ary[1], $ary[0]];
}
$i = $j = 0;
$mergedAry = [];
while ($i < count($sortedAry1) && $j < count($sortedAry2)) {
if ($sortedAry1[$i] <= $sortedAry2[$j]) {
$mergedAry[] = $sortedAry1[$i];
$i++;
} else {
$mergedAry[] = $sortedAry2[$j];
$j++;
}
}
while ($i < count($sortedAry1)) {
$mergedAry[] = $sortedAry1[$i];
$i++;
}
while ($j < count($sortedAry2)) {
$mergedAry[] = $sortedAry2[$j];
$j++;
}
return $mergedAry;
}
}