A few days ago, I wrote a simple Quicksort implementation in Common Lisp. After that, I started to wonder how other lisps and Perl compared for sorting numbers. Here are some of the assertions that we've all read on the Web and that I wanted to confirm:

• Perl is reasonably fast
• Some of the new Perl features that people are using these days (like autobox::Core and Moose) can sometimes take performance hit
• Elisp is slow
• PLT Scheme is slow

I wrote simple Quicksort implementations to confirm or dispel all of these statements and here are the benchmarks that I came up with for sorting 180,000 numbers:

• Perl: 1,717 ms
• Perl with autobox::Core -ish code: 5,533 ms (yeah, wow!)
• Elisp: 12,058 ms (again, wow!)
• PLT Scheme: 1,408 ms

For reference, from my previous article, Common Lisp measured in at a comfortable 513 ms.

Everything but the performance of the old-fashioned Perl code was a surprise to me. I was astonished to see the overhead that the autobox::Core functionality adds to the Perl program. I was quite surprised to find that PLT Scheme was faster than Perl. I was sorely disappointed with Elisp, which, as an avid Emacs lover, I use a great deal.

I'm sure a lot of you are going to know better ways to code this algorithm. If so, please post your code in the comments. Also, feel free to post code in languages other than the ones I've reviewed here. I'd love to see Python and Ruby in the mix, or a URI that points to a post that's already measured Quicksort performance of various programming languages.

The listings that follow contain all the code that I used for the Quicksort benchmarks. I never time the creation of the original list, but I wonder if there are other ways that I could time the code to make the benchmarks more fair.

---

Old-Fashioned Perl

#!/usr/bin/perl

use Time::HiRes qw/time/;
use strict;
use warnings;

my $n= shift;
$n= 180_000 unless $n;
print test(\&quicksort, $n), "\n";

sub quicksort {
  my @list= @_;
  if(@list < 2) {return @list}
  my $pivot= $list[int(rand(@list))];
  my (@less, @p, @more);
  for my $n (@list) {
    if($n < $pivot) {push @less, $n}
    elsif($n == $pivot) {push @p, $n}
    else {push @more, $n}}
  (quicksort(@less), @p, quicksort(@more))
}

sub test {
  my ($function, $n)= @_;
  my @list= map {int(rand($n))} (1 .. $n);
  my $t= time;
  my @sorted= quicksort(@list);
  sprintf("%d ms", (time - $t) * 1000);
}

---

Perl with autobox::Core Code

#!/usr/bin/perl

use Time::HiRes qw/time/;
use autobox::Core;
use Modern::Perl;

my $n= shift;
$n= 180_000 unless $n;
say test(\&quicksort, $n);

sub quicksort {
  my $list= shift;
  if($list->size < 2) {return $list}
  my $pivot= $list->[int(rand $list->size)];
  my ($less, $p, $more)= (+[], +[], +[]);
  for my $n ($list->flatten) {
    if($n < $pivot) {$less->push($n)}
    elsif($n == $pivot) {$p->push($n)}
    else {$more->push($n)}}
  (quicksort($less), $p, quicksort($more))
}

sub test {
  my ($function, $n)= @_;
  my $list= [1 .. $n]->map(sub {int rand $n});
  my $t= time;
  my $sorted= quicksort($list);
  sprintf("%d ms", (time - $t) * 1000);
}

---

PLT Scheme

#lang scheme

(define (quicksort list)
  (if (< (length list) 2) list
      (let ((p (list-ref list (random (length list)))))
        (append (quicksort (filter (lambda (x) (< x p)) list))
                (filter (lambda (x) (= x p)) list)
                (quicksort (filter (lambda (x) (> x p)) list))))))


(define (test n)
  (let ((list (rest (build-list n (lambda (x) (random n))))))
    (time (quicksort list))
    'done))

---

Emacs Lisp

(defun quicksort2 (list)
  (if (< (length list) 2) list
      (let ((p (nth (random (length list)) list)))
        (append (quicksort2 (remove-if-not (lambda (x) (< x p)) list))
                (remove-if-not (lambda (x) (= x p)) list)
                (quicksort2 (remove-if-not (lambda (x) (> x p)) list))))))

(defun test1 (n)
  (let ((list (loop for a from 1 to n collect (random n))))
    (first (time (quicksort2 list)))))