Engineering A Sort Function

February 23, 2010

We examined quicksort in a previous exercise. Today we examine a version of quicksort that Jon Bentley spoke about at Google, reprising the quicksort function that he and Doug McIlroy explained in their article “Engineering a Sort Function” in Software—Practice and Experience (Volume 23, Number 11, Pages 1249–1265, November 1993).

The Bentley/McIlroy quicksort is characterized by an adaptive pivot selection, a fast approaching-pointers partition, use of ternary comparison operator (less-than, equal-to, greater-than) to enable a “fat pivot,” and insertion sort for small sub-arrays. The quicksort also uses a fast swap that adapts to the size of the data elements. The adaptive pivot selection uses the middle element for small arrays, the median of the first, middle and last elements for medium-sized arrays, and the median of nine equally-spaced elements for larger arrays. This description doesn’t really do justice to the code; you should read the article for details.

Your task is to write a quicksort function using the same algorithm as Bentley and McIlroy. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: