Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
18 / 18
100.00% covered (success)
100.00%
2 / 2
 CRAP
100.00% covered (success)
100.00%
1 / 1
BitonicSort
100.00% covered (success)
100.00%
18 / 18
100.00% covered (success)
100.00%
2 / 2
 7
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
 merge
100.00% covered (success)
100.00%
12 / 12
100.00% covered (success)
100.00%
1 / 1
 4
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 * BitonicSort 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 BitonicSort 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        $first  = self::sort(\array_slice($list, 0, (int) ($n / 2)), SortOrder::ASC);
49        $second = self::sort(\array_slice($list, (int) ($n / 2)), SortOrder::DESC);
50
51        return self::merge(\array_merge($first, $second), $order);
52    }
53
54    /**
55     * Splitting, merging and sorting list
56     *
57     * @param array $list  List to sort
58     * @param int   $order Sort order
59     *
60     * @return array
61     *
62     * @since 1.0.0
63     */
64    private static function merge(array $list, int $order) : array
65    {
66        $n = \count($list);
67
68        if ($n === 1) {
69            return $list;
70        }
71
72        $dist = $n / 2;
73        for ($i = 0; $i < $dist; ++$i) {
74            if ($list[$i]->compare($list[$i + $dist], $order)) {
75                $old              = $list[$i];
76                $list[$i]         = $list[$i + $dist];
77                $list[$i + $dist] = $old;
78            }
79        }
80
81        $first  = self::merge(\array_slice($list, 0, (int) ($n / 2)), $order);
82        $second = self::merge(\array_slice($list, (int) ($n / 2)), $order);
83
84        return \array_merge($first, $second);
85    }
86}