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₂(N)) and the stack space consumption is bounded by O(log₂(N)) in the worst case. It uses exactly two extra elements to sort any number of elements in the input.
Download: sorting.tar.gz (14kB)

Description

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₂(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₂(N)) instead of the usual O(N²) for a plain Quicksort. The average performance is as good as that of plain Quicksort, i.e. O(N*log₂(N)), too. See

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

for the gory details.

Supported Compilers

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!