Jesse,
Both VADS and APEX provide *generic* versions of Quicksort, Heapsort and
Insertion sort in a package named "ordering". I wrote these about 12 years
ago and have used them successfully in numerous situations. The spec for
the package discusses tradeoffs, so I have copied it below.
You really need to do some analysis before picking the algorithm.
Are your objects large?

If they are very large then SWAPs will dominate COMPAREs and you need to
pick an algorithm that minimizes SWAPs. It may even pay to build an
"indirect" array, sort that, and then do only the MOVEs required.
What is the *guaranteed* maximum size?

If there is no limit, that excludes certain algorithms. If there is a fixed
limit, then some things can be done to make the algorithm faster, including
converting SWAPs to single MOVEs.
What is the stack or local space size restrictions?

If you have limited stack then before using Quicksort, you need to make sure
you have enough stack for when the algorithm encounters *worst* case inputs.
Quicksort is recursive and can go to a depth of O(N**2) if you are not
careful.
What is the *expected* sorting size?

If it is quite small, then you need to minimize OVERHEAD for your
algorithms, possibly at the expense of more COMPAREs or even more SWAPs.
Must you have reproducible times, i.e. times independent of the initial
ordering?


If so, then Quicksort is *NOT* appropriate. Quicksort has an *average*
O(NlnN) performance, but there are input patterns that can produce O(N**2)
and all values in between. The original Quicksort algorithm was worst case
for preSORTED data.
Will the list have *equal* values?

If the compare may have equal values, and you must have a "stable" sort,
then Insertion sort or some other O(N**2) algorithm is required. A stable
sort keeps the order of equal items. It is used when the list has already
been sorted by some other process or algorithm and it is important that the
original order not be disturbed by the new sort.
If you are sure the lists will never be more than 20 long, you need to
seriously look at the OVERHEAD for each algorithm. I'd suggest NOT using
Quicksort, since it only averages a speed of O(NlnN), and with only a few
entries, it is quite possible to have an input pattern that produces
O(N**2).
I've had good luck with Heapsort, which is guaranteed to be O(NlnN), but
that does not minimize MOVEs so you might want to try an "indirect" Heapsort
if your objects are of any significant size.
An "indirect" sort creates an array with the indices to be sorted. You then
sort the indices using them as indices into the original array. Finally you
walk the index array to determine where objects are to be located (you walk
it in a way that only requires one MOVE of the pointed to objects and only
for those that are "mislocated"  that in itself is an interesting little
algorithm.
Regards,
Steve
[log in to unmask]
 UNIT: package spec ORDERING
 FILES: ordering_s.a in verdixlib
 related file is ordering_b.a in verdixlib
 PURPOSE: provide ordering functions, including sorting and permuting
 DESCRIPTION: includes packages QUICKSORT, HEAPSORT, INSERTIONSORT,
 and PERMUTE.
 Usage: these packages are instantiated with the Element type
 of elements to be sorted, the Index discrete type
that
 indexes them, and the Boolean function on the
elements
 that orders them.



 package ORDERING

 Provides several sorting algorithms and a permuting algorithm, which are
 generic with respect to
 1. Element type in a List to be sorted, an arbitrary type.
 2. Index type for indexing into the List, a discrete type.
 A type List is defined from the Element type and the Index type.
 3. A relation (Boolean result function) between Elements of the List.
 For an ascending sort, the relation should be True whenever the
 first Element is strictly less than the second Element. For a
 descending sort, the relation should be True whenever the first
 Element is strictly greater than the second Element.
 Only "inplace" algorithms are provided, i.e. algorithms whose space
 requirement is N or ( N + log_2(N)*e ), where e is some small value. The
 log_2(N)*e additional space is taken from the stack.

 The following sorting algorithms are provided, and an indication is given
 about  when the algorithm should be chosen:
 1. Quicksort (medianofthree): least average sort time of all, but
 there are data organizations for which sorting time is O(N**2). the
 medianofthree approach is used for the split partition value, so
that
 sorted data is NOT a worst case data organization (unlike the basic
 quicksort algorithm).
 2. Heapsort: guaranteed O(NlnN) time. Note that the "heap" in this
 algorithm applies to the type of data structure applied to the
 list to be sorted; there is NO allocation of space from the heap.
 3. Insertion sort: one of the simplest sorts. It is O(N**2) in time
 complexity, but has the one advantage that it is stable, i.e. elements
 with equal values retain their order in the list.

 The following sorting algorithms are NOT provided. An indication of
 why the algorithms not provided is given.
 1. Shellsort (diminishing increments): This algorithm is consistently
 bettered by Heapsort, and usually bettered by Quicksort. Either of
 those should be used instead.
 2. Listmerge sort: This algorithm requires a special list that has a
 link field in each element that can hold an index value. Its major
 advantage is that it is a stable sort in O(NlnN) in time, i.e. it
 makes a reasonable timespace tradeoff to achieve a stable sort.
 However, its space requirements violate the "general element",
 "inplace" sort requirements defined for this package. A reasonable
 alternative to providing a stable sort in (NlnN) time is to add
 a single field to each initial element, initialized to the value
 of the element's position in the array, and make the "<" function
 include a compare of this field if the original compared fields
 are equal. Thus equal elements are forced nonequal, and the order
 of equal elements in the array is maintained.
 3. Bubblesort. This algorithm takes O(N**2) time, and has a higher
 constant factor than insertion sort.
 4. Selectionsort. This algorithm takes O(N**2), and is not stable
 when done inplace with exchanges, unless considerable complications
 are added to the algorithm.

 It is helpful to organize the sorting algorithms to aid understanding.
 The following taxonomy is based on the article:
 An Inverted Taxonomy of Sorting Algorithms, Susan M. Merritt,
 Communications of the ACM, Vol. 28, No. 1, January 1985, pp. 9699.

 All sorting algorithms are based on the abstraction "split into parts,
 sort the parts, join the sorted parts". Specific sorting algorithms are
 conveniently classified as hardsplit/easyjoin or easysplit/hardjoin,
 based on whether the "work" is done at the start or end of the algorithm.
 The abstract algorithm is clearly recursive. Usual programming style
 converts the recursions to iterations for speed.

 If we independently specify the splitting criteria then we get the
 following table:

 Splitting criteria hardsplit/easyjoin
easysplit/hardjoin
   

 Equalsized parts Quicksort Merge Sort
 One part is one element Selection Sort Insertion Sort
 One element, in place Bubble Sort Sinking Sort

 The Heapsort algorithm is viewed as a Selection Sort that minimizes
 the comparisons to find the next element by using a data structure
 (a heap). The Shell Sort algorithm is viewed as a version of the
 Insertion Sort that operates independently on various subsets of the
 input data. An additional class of algorithms* may be viewed as
 splitting criteria that are varying combinations of Quicksort with
 Bubble Sort. (Perhaps the combination of Merge Sort and Sinking Sort
 would give rise to a similar set of algorithms.)

 * A Class of Sorting Algorithms Based on Quicksort, Roger L. Wainwright,
 Communications of the ACM, Vol. 28, No. 4, April 1985, pp. 396403.



 package PERMUTE

 Provides a generic Permute package. The generic parameters are an
element
 of any type, an index of discrete type, and an ordering function. The
 package defines a list data type and procedure. The procedure takes a
 single argument of list type, and rearranges it to the next lexical
 permutation. The exception "no_more_permutations" is raised when the
 input list is lexically the last permutation.
 The algorithm is derived from that presented in Dijkstra's "A Discipline
of
 Programming".

.......................................................................... 

package ORDERING is
 hardsplit / easyjoin sorting algorithms
generic
type Element is private;
type Index is (<>);
with function "<" ( left, right: Element ) return Boolean is <>;
package QuickSort is
type List is array (Index range <>) of Element;
procedure QuickSort ( L: in out List );
end QuickSort;
pragma Share_Body ( QuickSort, False ) ;
generic
type Element is private;
type Index is (<>);
with function "<" ( left, right: Element ) return Boolean is <>;
package HeapSort is
type List is array (Index range <>) of Element;
procedure HeapSort ( L: in out List );
end HeapSort;
pragma Share_Body ( HeapSort, False ) ;
 easysplit / hardjoin sorting algorithms
generic
type Element is private;
type Index is (<>);
with function "<" ( left, right: Element ) return Boolean is <>;
package InsertionSort is
type List is array (Index range <>) of Element;
procedure InsertionSort ( L: in out List );
end InsertionSort;
pragma Share_Body ( InsertionSort, False ) ;
 permute list to next lexical permutation algorithm
generic
type Element is private;
type Index is (<>);
with function "<=" (left, right: Element) return Boolean is <>;
package Permute is
type List is array (Index range <>) of Element;
procedure Permute ( L: in out List );
No_more_permutations : exception ;
end Permute ;
pragma Share_Body ( Permute , False ) ;
end ORDERING;

.......................................................................... 


 DISTRIBUTION AND COPYRIGHT:

 This software is copyright 1985 by the VERDIX Corporation.
 All rights reserved. No part of the material protected by
 this copyright notice may be reproduced or utilized in any
 form without written permission of the copyright owner.

 DISCLAIMER:

 This software and its documentation are provided "AS IS" and
 without any expressed or implied warranties whatsoever.
 No warranties as to performance, merchantability, or fitness
 for a particular purpose exist.

 Because of the diversity of conditions and hardware under
 which this software may be used, no warranty of fitness for
 a particular purpose is offered. The user is advised to
 test the software thoroughly before relying on it. The user
 must assume the entire risk and liability of using this
 software.

 In no event shall any person or organization of people be
 held responsible for any direct, indirect, consequential
 or inconsequential damages or lost profits.
