fastsort.txt
Leks van der Voort van der Kleij, Meppel, Netherlands, acgrid@planet.nl
January 13th 2006
----
Note: If you post email to me on this subject, please be sure to put the keyword
      fastsort in the subject field. Otherwise your message might not be read,
      because I use filtering on subjects.
----

----              Fast sorting functions for Euphoria                       ----

Development history

In writing a 3D simulation program, I needed a fast sorting function to sort
sometimes huge sequences of vertices (3D float coordinates). Of course I did
not want to write my own sorting routines, while sort.e being available in
Euphoria\ Include.

I was rather disappointed that my program crashed once in a while. I noticed
that this happens when during execution my program tried to sort a sequence of
lenght 1 or length 0. So I take a look at the code, and solved this problem by
prepending an "exception catch" :

           last = length(x)
           if last < 2
              then return x
           end if

(Note: don't bother the usage of the variable 'last' here: it is used in the
remainder of the function, so not an superfluous assignment !!)

That problem being solved, I took a closer look at the code. I did not fully
understand it immediately. Because it was a long time since I bothered about
sorting routines, I decided to read on this subject in "good old" N. Wirth's
book "Algorithms & Data Structures = Programs". I learned two things:

1.
The shell sort (as used by sort in sort.e, named after its inventor Mr. Shell)
uses a kind of "backtracking" to check if insertion must be done in the sequence
before the left position of the actual gap. When sequences are big and the gap
is small (on the last steps of the sorting process) this backtracking can cost
many compare-operations, which are time consuming. So the sorting function must
implement a well chosen gap strategy, in order to prevent unnecassery
backtracking. Realising this implies that after a view first passes through the
sequence, the sequence is roughly sorted. Then most comparisons will lead to "
succes " (no changes needed). So if we want to gain execution speed we have to
a) optimize the program flow, so that the "success" case executes fastest
b) implement the best possible gap strategy

I optimized the program flow on the "old fashioned" way, using pencil and paper.
The resulting code (presented in new_shell_sort(), which can be found inside the
program testMySorts.exe) yields a speed gain of 7% - 10%, compared with the "
standard" shell sort in sort.e

Next I implemented Knuth's {1, 4, 13, 27, ...} (in reversed order) gap strategy
( gap(n+1) = 3*gap(n)+1 in this sequence). In order to prevent calculation
during the sorting, the function starts with building a lookup table, depending
on the size of the sequence that has to be sorted.

These two enhancements combined, resulted in a speed gain of up to 25%. The code
can be found in the function lut_shell_sort(). However with sequences of length
greater then ca 10000, this function becomes slower than the original one.

So: what to do?

2.
Wirth stated and tested that quicksort (named so by its inventor Mr. Hoare
because of its speed) is the fastest array sorting algorithm. But it can degrade
seriously in (may be rare) cases with a wrong choice of the median value to
start with. But when I did Euphoria's ALLSORTS.ex test, the results of quicksort
were rather disappointing. How can that be?? Studying the code, I learned that
this implementation uses recursive calls to itself at each refinement stage.
Might the recursion cause the lack of speed?

I decided to implement Wirth's PASCAL version of quicksort without recursion in
Euphoria, and checked and  measured it in the ALLSORTS framework. For sequences
of size above 500 items, it  becomes faster than even my improved shell sort.
With 40,000 items I gained up to 40% speed.

Next I implemented a "best guess" algorithm for the choice of the first median
value for sorting. And I made a short cut for the sort of very small sequences
with length 2 and 3. Wondering why that would benefit? Well, in quicksort each
refinement yields two shorter sequences to be sorted, so you will ever end up
with small sequences to sort: so let that be fast.

And it payed off. Now I got a speed gain of up to 45% for 80,000 items.
Quicksort is the fastest for sequences above 320 items, lut_shell_sort for
sequences below 320 items.

So I created a "wrapper" sort(), which chooses the right sort function,
depending on the size of the sequence to be sorted.


Because the generic "compare" of sequences might be more time consuming then
direct coded comparing of atoms (e.g. x[i] > x[j]), I also made "atomic"
versions of these sorting functions, which runs even 5% - 10% faster. However
they are restricted to sequences of atoms.

These functions and their "wrapper" asort() are also included.

At the end of the day (you might as well say "week") I ended up with sorting
functions that can sort up to 50% faster than the original sort.


Installation notes:

Having unzipped the package you will find the file sort.e
In your directory Euphoria\Include rename sort.e to org_sort.e (or whatever)
Copy my file sort.e into Euphoria\Include.

Note: I also included the function custom_sort() in my version of sort.e, so my 
file sort.e provides full compatibility with the original sort.e

Run your programs which use sort() and they should work as usual.
In programs that need even faster sorting of atom sequences, you can now use 
asort() as well, but your program is not anymore full compatible with the 
Euphoria standard.

Like to evaluate first how these new routines on your own system? Just run 
testMySorts.ex : no previous insertion of the new sort.e in the Include 
directory is needed for this evaluation.


Legal note:
The functions are provided "as is". You can use and distribute them freely.
In case of distribution. please distribute the entire fastsort.zip package

Disclaimer:
The author can not be held responsible for any damage that might occur using 
these functions


