## Ada 95 Sorting Routines |

**Abstract**- Package
`TW_Sorting`

implements fast and correct Quicksort. Three different interfaces are provided. The implementation has an average*and*worst-case performance of**O(N*log**and the stack space consumption is bounded by_{2}(N))**O(log**in the worst case. It uses exactly_{2}(N))*two*extra elements to sort any number of elements in the input.

**Download**`sorting.tar.gz`

(14kB)

I wrote this software because I one day needed to have a fast
sorting algorithm, but all existing Quicksort implementations I
came across were badly implemented: they used too much stack space,
had a poor choice for the pivot, or even failed some of the tests in
sort_test.adb (in particular those where the input's array bounds
include Index_Type'Last, which makes a lot of sorting routines raise
`CONSTRAINT_ERROR`

because they carelessly step an index
beyond its range).

Limiting the stack space needed by Quicksort to O(log_{2}(N)) is
so simple that any published Quicksort version should do it. It suffices
to sort the larger partition iteratively, and only recurse on the smaller
partition. A Quicksort that sorts both partitions recursively is in my
eyes simply not worth bothering with.

The commonly agreed-upon "best" choice for the pivot is taking the median of the first, middle and last element of the array that is to be sorted. (More elaborate schemes have been proposed, but their overhead outweighs the perfomance gains one might get due to better partitioning.) A Quicksort that uses just the middle element as the pivot is just not up to date.

And of course, a Quicksort that cannot corrctly handle boundary cases such as an array index range that includes the largest value of the index type's base type is worse than no Quicksort at all. (Because such subtle bugs will bite you when you expect it the least.)

The sorting library provided here has none of these problems. In fact,
it implements a so-called *Introspective Sort*, which has the nice
property that its worst-case performance is O(N*log_{2}(N)) instead
of the usual O(N^{2}) for a plain Quicksort. The *average
performance* is as good as that of plain Quicksort, i.e.
O(N*log_{2}(N)), too. See

Musser, D.R.: "Introspective Sorting and Selection Algorithms",Software - Practice & Experience (8), pp. 983-993; 1997.

for the gory details.

This library compiles and passes all tests with the following compilers:

- GNAT 3.12a3 on Win NT
- ObjectAda 7.1.1 on Win NT

The code is OS independent; it should run OK on any platform. If you find
a compiler that does *not* compile the library or that
*fails* the test program, let
me know, please!

Copyright © 2000 by
Thomas Wolf. All rights
reserved.
TW, Jul 25, 2000 |