Building quicksort with php

Question

I recently read about quicksort and was woudering whether it would be smart to build my own function to sort things with quicksort or if it would be inefficent. What do you think is the built in sort function better than a selfbuilt quicksort function?

Answer 1

Stick with the built-in sort function. Quicksort is a simple algorithm, but to get good performance on computers that are actually in use requires a little bit of finesse. It is more than likely that the built-in function is already more optimized than anything you would write in a reasonable amount of time. (The constant-factor speedup from being written in C instead of PHP is also probably helpful.)

If you are sorting so many elements that you are slowed down by the sort function, you are probably doing something wrong. (This is PHP after all. You should use a general-purpose language for data-intensive processing. It will be easier to write your code, and it will run faster.)

Answer 2

From http://php.net/sort

Note: Like most PHP sorting functions, sort() uses an implementation of » Quicksort.

The core PHP functions will be implemented in c, rather than PHP, so they should generally be significantly faster than anything you can write yourself in PHP. There will be cases where it is faster to write your own, but I guess these would be when you have a very specific case and you can make your own specific optimisations for that. I think that is unlikely to be the case here.

Answer 3

In fact I did this for a data point on a presentation I am putting together. The test sorts an array of 250,000 integers using the native sort function and an implementation of the quicksort algorithm written in php. The contents of the array are exactly the same for both runs, the data is randomized, and the time reported is only for performing the sort, not other processing necessary to invoke the php interpreter.

Results:

  Native sort implementation:  1.379 seconds
PHP quicksort implementation: 30.615 seconds

Definitely use the native implementation. That should be the case for any interpreted language.

The results for the other languages I tested with the same conditions using the same implementation on the same hardware and OS, provide an interesting performance comparison and put the PHP result in perspective:

               C: 0.107 seconds
            Java: 0.250 seconds
JavaScript (FF3): 4.401 seconds

Notably, Chrome and Safari performed much faster for the JavaScript test, but I don't include those here because those tests were recorded in a different environment.

Answer 4

For reference there is a PHP implementation here:

http://en.wikibooks.org/wiki/Algorithm%5Fimplementation/Sorting/Quicksort#C.23