Узнал про timsort, решил реализовать его на пхп, появилось несколько вопросов. На википедиях и статьях, сортировку делят на 3 этапа, я реализовал их в классе вот так:
class Tim
{
public $arr = [2, 5, 3, 8, 10, 200, 1];
public $pivot;
public $min = [];
public $great = [];
public function sort($arr)
{
// 1) Делим массив на 2 подмассива, в min - меньшие, в great - большие
if (count($arr) <= 1) return $arr;
$this->pivot = floor(count($arr) / 2);
for ($i = 0; $i < count($arr); $i++) {
if ($i == $this->pivot) continue;
if ($arr[$i] < $arr[$this->pivot]) {
$this->min[] = $arr[$i];
}
if ($arr[$i] > $arr[$this->pivot]) {
$this->great[] = $arr[$i];
}
}
// 2) Сорируем эти массивы пузырьком
for ($i = 0; $i < count($this->min) - 1; $i++) {
for ($j = $i + 1; $j < count($this->min); $j++) {
if ($this->min[$i] > $this->min[$j]) {
$tmp = $this->min[$i];
$this->min[$i] = $this->min[$j];
$this->min[$j] = $tmp;
}
}
}
for ($i = 0; $i < count($this->great) - 1; $i++) {
for ($j = $i + 1; $j < count($this->great); $j++) {
if ($this->great[$i] > $this->great[$j]) {
$tmp = $this->great[$i];
$this->great[$i] = $this->great[$j];
$this->great[$j] = $tmp;
}
}
}
// 3) Соединяем массивы
return array_merge($this->min, [$this->arr[$this->pivot]], $this->great);
}
}
На просторах интернета не нашел простого примера, где бы поэтапно рассказывалось бы про эту сортировку и одновременно показывали пример на пхп, поэтому я попробовал реализовать её сам, правильно ли я сделал?
Если да, то по логике, получившиеся массивы(с минимальными и большими значениями) мы сортируем пузырьковой сортировкой, что разве не должно замедлять её?
Простой