편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
168번째 줄: | 168번째 줄: | ||
<syntaxhighlight lang='php'> | <syntaxhighlight lang='php'> | ||
<?php | <?php | ||
function merge_sort(&$a) { | function merge_sort(&$a, $left=0, $right=null) { | ||
$ | if( is_null($right) ) $right=count($a)-1; | ||
if( $ | if( $left>=$right ) return; | ||
$ | $middle = intdiv($left+$right-1, 2); | ||
merge_sort($a, $left, $middle); | |||
merge_sort($a, $middle+1, $right); | |||
$n1 = $middle + 1 - $left; | |||
$n2 = $right - $middle; | |||
$L = array_fill(0, $n1, 0); | |||
$R = array_fill(0, $n2, 0); | |||
if | for($i=0; $i<$n1; $i++) $L[$i] = $a[$left+$i]; | ||
$ | for($i=0; $i<$n2; $i++) $R[$i] = $a[$middle+1+$i]; | ||
$k = $left; | |||
$i = $j = 0; | |||
while( $i<$n1 && $j<$n2 ) { | |||
if( $L[$i]<=$R[$j] ) { $a[$k] = $L[$i]; $i++; $k++; } | |||
else { $a[$k] = $R[$j]; $j++; $k++; } | |||
} | } | ||
while( $i<$n1 ) { $a[$k]=$L[$i]; $i++; $k++; } | |||
while( $j<$n2 ) { $a[$k]=$R[$j]; $j++; $k++; } | |||
} | } | ||
$arr = [9,1,22,4,0,-1,1,22,100,10]; | $arr = [9,1,22,4,0,-1,1,22,100,10]; |