The following are implementations of the various sorting algorithms with comments. They include:

• A basic algorithm,
• A reasonably optimized array-based algorithm, and
• A reasonably optimized pointer-based algorithm.

Improvements are welcome and will be appropriately referenced: improvements to the basic algorithm include any changes which better demonstrate the algorithm, while improvements to the optimized algorithms require a reasonable increase in speed or decrease in memory usage.

Each function has two calling sequences:

• sort( Type *array, int n )
• sort( Type *array, int lower, int upper )
• sort( Type *lower, Type *upper )

where in the first case, n is the size of the array; in the second, the array is to be sorted on the range lower, ..., upper inclusive; and in the third, the two point to the bounds of the addresses to be sorted inclusive. In general, the first algorithm calls either algorithm_internal( array, 0, n - 1 ) or algorithm_internal( array, array + n - 1 ), respectively.

The namespace structure is as follows:

• All objects are within the Sorting_algorithms namespace,
• Each algorithm is within the appropriate Sorting_algorithm::Algorithm_name namespace, and
• Each algorithm has up to three implementations, represented by classes, for a basic implementation, an enhanced array-based implementation, and an enhanced pointer-based implementation.

A testing framework has also been developed. The guidelines for the three implementations--basic, array, and pointer--are that:

• The basic implementation demonstrates most clearly the algorithm with no optimizations,
• The enhanced array-based implementation makes various improvements but is still array based and does not use any side effects, e.g., array[i]; ++i; is preferred to array[i++];, and
• The enhanced pointer-based implementation has no such restrictions.

The interfaces depend upon the following grid:

	Class-based	Procedural
Basic	Named_sort_basic.h void Sorting_algorithms::Named_sort::Basic::    sort( Type *array, int n )	Named_sort_basic_code_only.h void    named_sort( Type *array, int n )
Enhanced Array- based	Named_sort_array.h void Sorting_algorithms::Named_sort::Array::    sort( Type *array, int n )    sort( Type *array, int a, int b )	Named_sort_array_code_only.h void    named_sort( Type *array, int n )    named_sort( Type *array, int a, int b )
Enhanced Pointer- based	Named_sort_pointer.h void Sorting_algorithms::Named_sort::Pointer::    sort( Type *array, int n )    sort( Type *array, int a, int b )    sort( Type *first, Type *last )	Named_sort_pointer_code_only.h void    named_sort( Type *array, int n )    named_sort( Type *array, int a, int b )    named_sort( Type *first, Type *last )

To Do

Shell sort, iterative merge sort, radix sort with more than two values, introspective sort, and bucket sort.