Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
38 / 38
100.00% covered (success)
100.00%
3 / 3
 CRAP
100.00% covered (success)
100.00%
1 / 1
MergeSort
100.00% covered (success)
100.00%
38 / 38
100.00% covered (success)
100.00%
3 / 3
 13
100.00% covered (success)
100.00%
1 / 1
 __construct
n/a
0 / 0
n/a
0 / 0
 1
 sort
100.00% covered (success)
100.00%
6 / 6
100.00% covered (success)
100.00%
1 / 1
 2
 sortHalve
100.00% covered (success)
100.00%
6 / 6
100.00% covered (success)
100.00%
1 / 1
 2
 merge
100.00% covered (success)
100.00%
26 / 26
100.00% covered (success)
100.00%
1 / 1
 8
1<?php
2/**
3 * Jingga
4 *
5 * PHP Version 8.1
6 *
7 * @package   phpOMS\Algorithm\Sort;
8 * @copyright Dennis Eichhorn
9 * @license   OMS License 2.0
10 * @version   1.0.0
11 * @link      https://jingga.app
12 */
13declare(strict_types=1);
14
15namespace phpOMS\Algorithm\Sort;
16
17/**
18 * MergeSort class.
19 *
20 * @package phpOMS\Algorithm\Sort;
21 * @license OMS License 2.0
22 * @link    https://jingga.app
23 * @since   1.0.0
24 */
25final class MergeSort implements SortInterface
26{
27    /**
28     * Constructor
29     *
30     * @since 1.0.0
31     * @codeCoverageIgnore
32     */
33    private function __construct()
34    {
35    }
36
37    /**
38     * {@inheritdoc}
39     */
40    public static function sort(array $list, int $order = SortOrder::ASC) : array
41    {
42        $n = \count($list);
43
44        if ($n < 2) {
45            return $list;
46        }
47
48        $clone = $list;
49        self::sortHalve($clone, 0, $n - 1, $order);
50
51        return $clone;
52    }
53
54    /**
55     * Recursive sorting of halve of the list and then merging it
56     *
57     * @param array $list  Data to sort
58     * @param int   $lo    Start of the list to sort
59     * @param int   $hi    End of the list to sort
60     * @param int   $order Sort order
61     *
62     * @return void
63     *
64     * @since 1.0.0
65     */
66    private static function sortHalve(array &$list, int $lo, int $hi, int $order) : void
67    {
68        if ($lo >= $hi) {
69            return;
70        }
71
72        $mi = (int) ($lo + ($hi - $lo) / 2);
73
74        self::sortHalve($list, $lo, $mi, $order);
75        self::sortHalve($list, $mi + 1, $hi, $order);
76
77        self::merge($list, $lo, $mi, $hi, $order);
78    }
79
80    /**
81     * Merge and sort sub list
82     *
83     * @param array $list  Data to sort
84     * @param int   $lo    Start of the list to sort
85     * @param int   $mi    Middle point of the list to sort
86     * @param int   $hi    End of the list to sort
87     * @param int   $order Sort order
88     *
89     * @return void
90     *
91     * @since 1.0.0
92     */
93    private static function merge(array &$list, int $lo, int $mi, int $hi, int $order) : void
94    {
95        $n1 = $mi - $lo + 1;
96        $n2 = $hi - $mi;
97
98        $loList = [];
99        $hiList = [];
100
101        for ($i = 0; $i < $n1; ++$i) {
102            $loList[$i] = $list[$lo + $i];
103        }
104
105        for ($i = 0; $i < $n2; ++$i) {
106            $hiList[$i] = $list[$mi + 1 + $i];
107        }
108
109        $i = 0;
110        $j = 0;
111        $k = $lo;
112
113        while ($i < $n1 && $j < $n2) {
114            if (!$loList[$i]->compare($hiList[$j], $order)) {
115                $list[$k] = $loList[$i];
116                ++$i;
117            } else {
118                $list[$k] = $hiList[$j];
119                ++$j;
120            }
121
122            ++$k;
123        }
124
125        while ($i < $n1) {
126            $list[$k] = $loList[$i];
127            ++$i;
128            ++$k;
129        }
130
131        while ($j < $n2) {
132            $list[$k] = $hiList[$j];
133            ++$j;
134            ++$k;
135        }
136    }
137}