Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
93.02% covered (success)
93.02%
40 / 43
0.00% covered (danger)
0.00%
0 / 1
 CRAP
0.00% covered (danger)
0.00%
0 / 1
TimSort
93.02% covered (success)
93.02%
40 / 43
0.00% covered (danger)
0.00%
0 / 1
 15.08
0.00% covered (danger)
0.00%
0 / 1
 sort
93.02% covered (success)
93.02%
40 / 43
0.00% covered (danger)
0.00%
0 / 1
 15.08
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 * TimSort 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 TimSort implements SortInterface
26{
27    /**
28     * Blocks the sorting is divided into
29     *
30     * @var int
31     * @since 1.0.0
32     */
33    private const BLOCKS = 32;
34
35    /**
36     * {@inheritdoc}
37     */
38    public static function sort(array $list, int $order = SortOrder::ASC) : array
39    {
40        $n = \count($list);
41
42        if ($n < 2) {
43            return $list;
44        }
45
46        for ($lo = 0; $lo < $n; $lo += self::BLOCKS) {
47            // insertion sort
48            $hi = \min($lo + 31, $n - 1);
49            for ($j = $lo + 1; $j <= $hi; ++$j) {
50                $temp = $list[$j];
51                $c    = $j - 1;
52
53                while ($c >= $lo && $list[$c]->compare($temp, $order)) {
54                    $list[$c + 1] = $list[$c];
55                    --$c;
56                }
57
58                $list[$c + 1] = $temp;
59            }
60        }
61
62        for ($size = self::BLOCKS; $size < $n; $size *= 2) {
63            for ($lo = 0; $lo < $n; $lo += 2 * $size) {
64                // merge sort
65                $mi = $lo + $size - 1;
66                $hi = \min($lo + 2 * $size - 1, $n - 1);
67
68                $n1 = $mi - $lo + 1;
69                $n2 = $hi - $mi;
70
71                $loList = [];
72                $hiList = [];
73
74                for ($i = 0; $i < $n1; ++$i) {
75                    $loList[$i] = $list[$lo + $i];
76                }
77
78                for ($i = 0; $i < $n2; ++$i) {
79                    $hiList[$i] = $list[$mi + 1 + $i];
80                }
81
82                $i = 0;
83                $j = 0;
84                $k = $lo;
85
86                while ($i < $n1 && $j < $n2) {
87                    if (!$loList[$i]->compare($hiList[$j], $order)) {
88                        $list[$k] = $loList[$i];
89                        ++$i;
90                    } else {
91                        $list[$k] = $hiList[$j];
92                        ++$j;
93                    }
94
95                    ++$k;
96                }
97
98                while ($i < $n1) {
99                    $list[$k] = $loList[$i];
100                    ++$i;
101                    ++$k;
102                }
103
104                while ($j < $n2) {
105                    $list[$k] = $hiList[$j];
106                    ++$j;
107                    ++$k;
108                }
109            }
110        }
111
112        return $list;
113    }
114}