Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save andrewdalpino/377eada92e2a2a7129557479cc734ec7 to your computer and use it in GitHub Desktop.
Save andrewdalpino/377eada92e2a2a7129557479cc734ec7 to your computer and use it in GitHub Desktop.
<?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);
@andrewdalpino
Copy link
Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment