SortableArray.php

<?php

class SortableArray {
  private $content;
  private $length;

  function __construct(int ...$items) {
    $this->content = $items;
    $this->length = count($items);
  }

  public function toArray(): array {
    return $this->content;
  }

  /**
   * Bubble Sort
   */
  public function bubbleSort(): SortableArray {
    for ($i = 0; $i < $this->length - 1; $i++) {
      for ($j = $this->length - 1; $j > $i; $j--) {
        if ($this->content[$j] > $this->content[$i]) {
          $this->swap($i, $j);
        }
      }
    }

    return $this;
  }

  /**
   * Insertion Sort
   */
  public function insertionSort(): SortableArray {
    for ($i = 1; $i < $this->length; $i++) {
      $key = $this->content[$i];
      $j = $i - 1;
      while ($j >= 0 && $this->content[$j] > $key) {
        $this->content[$j + 1] = $this->content[$j];
        $j--;
      }

      $this->content[$j + 1] = $key;
    }

    return $this;
  }

  /**
   * Quick Sort
   */
  public function quickSort(int $left, int $right): SortableArray {
    if ($left < $right) {
      $pivotIndex = $this->partition($left, $right);
      $this->quickSort($left, $pivotIndex - 1);
      $this->quickSort($pivotIndex + 1, $right);
    }

    return $this;
  }

  /**
   * Merge Sort
   */
  public function mergeSort(int $left, int $right): SortableArray {
    if ($left < $right) {
      $center = floor(($left + $right) / 2);
      $this->mergeSort($left, $center);
      $this->mergeSort($center + 1, $right);
      $this->merge($left, $center, $right);
    }

    return $this;
  }

  private function merge(int $left, int $center, int $right) {
    $leftContent = array_slice($this->content, $left, $center - $left + 1);
    $rightContent = array_slice($this->content, $center + 1, $right - $center);
    array_push($leftContent, INF);
    array_push($rightContent, INF);
    $leftCursor = 0;
    $rightCursor = 0;

    for ($i = $left; $i <= $right; $i++) {
      if ($leftContent[$leftCursor] <= $rightContent[$rightCursor]) {
        $this->content[$i] = $leftContent[$leftCursor++];
      } else {
        $this->content[$i] = $rightContent[$rightCursor++];
      }
    }
  }

  private function partition(int $left, int $right): int {
    $pivot = $this->content[$right];
    $cursor = $left - 1;

    for ($i = $left; $i < $right - 1; $i++) {
      if ($this->content[$i] <= $pivot) {
        $cursor++;
        $this->swap($cursor, $i);
      }
    }
    $this->swap($cursor + 1, $right);

    return $cursor + 1;
  }

  private function swap(int $key1, int $key2) {
    $temp = $this->content[$key1];
    $this->content[$key1] = $this->content[$key2];
    $this->content[$key2] = $temp;
  }
}

$numbers = new SortableArray(2, 3, 4, 6, 8, 1, 9, 5);
print_r($numbers->mergeSort(0, 7)->toArray());