PHP - Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

<?php

function mergeSort(array &$A, int $lo, int $hi) {
  if ($hi - $lo < 2) return; // 单区间自然有序
  $mi = ($lo + $hi) >> 1; // 取中
  mergeSort($A, $lo, $mi); // 深入左区间 [$lo, $mi)
  mergeSort($A, $mi, $hi); // 深入右区间 [$mi, $hi)
  merge($A, $lo, $mi, $hi); // 二路归并
}

function merge(array &$A, int $lo, int $mi, int $hi) {
  $l_len = $mi - $lo; // 左区间长度
  // 取出左区间元素
  $B = array();
  for ($i = 0; $i < $l_len; $i++) $B[$i] = $A[$lo + $i];

  $r_len = $hi - $mi; // 右区间长度

  for ($i = 0, $l = 0, $r = 0; ($l < $l_len) || ($r < $r_len);) {
    // (左区间未越界) and
    // ((右区间越界，即左区间元素有剩余，右区间已取完) or (左区间元素 <= 右区间元素, 此时右区间未越界))
    if ($l < $l_len && ($r >= $r_len || $B[$l] <= $A[$mi + $r])) {
      $A[$lo + $i] = $B[$l];
      $i++; $l++;
    }

    // (右区间未越界) and
    // ((左区间越界，即右区间元素有剩余，左区间已取完) or (右区间元素 <= 左区间元素, 此时左区间未越界))
    if ($r < $r_len && ($l >= $l_len || $A[$mi + $r] <= $B[$l])) {
      $A[$lo + $i] = $A[$mi + $r];
      $i++; $r++;
    }
  }

  unset($B);
}

$A = [100, 5, 25, 29, 11, 65, 33, 22, 68, 19];

mergeSort($A, 0, count($A));

for ($i = 0; $i < count($A); $i++) echo $A[$i] . ' ';