Created
March 8, 2018 09:42
-
-
Save andrewdalpino/377eada92e2a2a7129557479cc734ec7 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
$n = $argv[1] ?? 1000; | |
$data = [ | |
// | |
]; | |
/** | |
* Sort an array by recursively merging a left and right sub array in order. | |
* O(N log N) time and O(N) space complexity. | |
* | |
* @param array $data | |
* @return array | |
*/ | |
function msort(array $data = []) : array | |
{ | |
$count = count($data); | |
if ($count < 2) { | |
return $data; | |
} | |
$left = msort(array_splice($data, 0, ceil($count / 2))); | |
$right = msort($data); | |
$counter1 = 0; | |
$counter2 = 0; | |
$sorted = []; | |
foreach (range(0, $count - 1) as $i) { | |
if ($counter1 === count($left)) { | |
$sorted[$i] = $right[$counter2]; | |
++$counter2; | |
} else if (($counter2 === count($right)) || ($left[$counter1] < $right[$counter2])) { | |
$sorted[$i] = $left[$counter1]; | |
++$counter1; | |
} else { | |
$sorted[$i] = $right[$counter2]; | |
++$counter2; | |
} | |
} | |
return $sorted; | |
} | |
echo 'Sorting ' . number_format($n) . ' random integers between -5000 and 5000' . "\n"; | |
foreach (range(0, $n - 1) as $i) { | |
$data[$i] = rand(-5000, 5000); | |
} | |
echo 'Testing native PHP quicksort ... '; | |
$start = microtime(true); | |
sort($data); | |
echo 'done in ' . (string) round(microtime(true) - $start, 5) . ' seconds.' . "\n"; | |
foreach (range(0, $n - 1) as $i) { | |
$data[$i] = rand(-5000, 5000); | |
} | |
echo 'Testing merge sort ... '; | |
$start = microtime(true); | |
$sorted = msort($data); | |
echo 'done in ' . (string) round(microtime(true) - $start, 5) . ' seconds.' . "\n"; | |
readline('Press any key to dump results ... '); | |
var_dump($sorted); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Results:
Sorting 1,000 random integers between -5000 and 5000
Testing native PHP quicksort ... done in 0.00019 seconds.
Testing merge sort ... done in 0.00246 seconds.