LampSort, a non-recursive QuickSort implementation

The divide and conquer partitioning is at the heart of QuickSort

Yesterday I came across a blog entry by Bertrand Meyer (of Eiffel fame) titled ‘Lampsort’. In it he discusses an alternative QuickSort implementation used by Leslie Lamport (of Latex fame) as an example during talks. I was curious and tried to implement the algorithm in Pharo, where I think the idea comes out very beautifully.

The Heart of QuickSort

We all know QuickSort as an elegant recursive sorting algorithm. However, the recursion is not fundamental to the algorithm, it is just an implementation detail. It is possible to think differently about QuickSort and to implement it without recursion. This is LampSort.

At its heart, QuickSort is a divide and conquer algorithm: it takes a big problem and reduces it in smaller problems over and over again until the parts get so small that they are trivial to solve.

The fundamental step of QuickSort is the partition operation. Given an interval [start, stop] over the data array that we have to sort, partition does the following:

• pick a pivot, any element inside the interval, let’s pick the first one
• split the interval in two sub intervals: one containing the elements smaller than the pivot and one containing the elements larger than the pivot
• continue on the 2 sub intervals
• intervals with zero or one element are sorted by default

The second step can be done elegantly and efficiently in-place with a single iteration over the interval, swapping elements if needed. Details about the partition operation can be found in the Wikipedia article. Note that the pivot itself is part of none of the sub intervals.

The third step, to continue on the 2 sub intervals, is traditionally expressed using recursion. But there is an other way to implement this step.

We can make the interval an actual object and track the work that we have to do using a set holding intervals.

Here is the algorithm:

• start by adding the complete interval to the set
• each time we partition, we take an interval out of the set, split it and add the 2 sub intervals
• empty or singleton intervals need no further work and get removed from the set
• eventually the set will be empty and we’re done !

The intervals track where we have to work, the actual data array is sorted in-place as we go. At the end, the array will be completely sorted.

Pharo Code

Let’s create a new class that will hold our LampSort implementation, with data as an instance variable.

Object subclass: #LampSort
  instanceVariableNames: 'data'
  classVariableNames: ''
  category: 'LampSort'

And generate basic accessors.

data
  ^ data
data: sequenceableCollection
  data := sequenceableCollection

For users, the main entry point will be the following method that destructively sorts its argument.

sort: sequenceableCollection
  ^ self 
      data: sequenceableCollection;
      sort;
      data

Which will get invoked like this, where we copy a literal constant:

LampSort new sort: #(7 12 3 20 5 8 2) copy.

Sort implements the core of LampSort, the iteration that replaces the recursion.

sort
  | intervals one |
  intervals := Set with: (1 to: data size).
  [ intervals isEmpty ]
    whileFalse: [ 
      one := intervals anyOne.
      one size > 1
        ifTrue: [ intervals addAll: (self partition: one) ].
      intervals remove: one ]

The #to: message creates intervals. Note the use of #anyOne — it really does not matter which interval is taken. Empty or singleton intervals are not processed further and just get removed.

The final step is the partition operation.

partition: interval
  | pivot index |
  pivot := data at: interval first.
  data swap: interval first with: interval last.
  index := interval first.
  interval first to: interval last — 1 do: [ :each | 
    (data at: each) < pivot
      ifTrue: [ 
        data swap: each with: index.
        index := index + 1 ] ].
  data swap: interval last with: index.
  ^ { interval first to: index — 1. index + 1 to: interval last }

The first element of the interval is taken as pivot. The pivot is first moved out of the way to the end of the interval.

Next, a single pass is made over the interval. Elements smaller that the pivot are moved forward. Certain elements will be swapped more than once. Elements equal to the pivot end up in the right sub interval, in possibly random positions.

Finally, the pivot is moved in place. This position indicates where the interval needs to be split in 2 sub intervals. We return an array containing the 2 sub intervals. Note that the pivot is excluded from either interval.

Getting the code

If you want to play with the code yourself, you can clone the GitHub repository https://github.com/svenvc/lampsort.git. Open Pharo 3 or 4 and use the Monticello Browser to add a FileTree repository.

Select the LampSort package and load it. Navigate to the LampSort class or LampSortTests unit tests.

The Next Step

In a followup article, LampSort Revisted, Visualised, object logging, agile visualisation and advanced tools are combined to get amazing insight into the LampSort code, easily.