Three implementations are provided:

• Pseudo code,
• A basic implemenation of the pseudo code,
• An enhanced implementation, and
• A pointer-based implementation.

When compiled with the -O2 option, the basic implementation sorts an array of size 200 million in 27 seconds, the enhanced array-based implementation sorts the same list in 25 seconds, and the pointer-based implementation sorts the list in 22 seconds.

For now, see the source directory.

Pseudo Code

Basic Implementation

template <typename Type> void quick_sort_recursive( Type *const, int const, int const, int const );
template <typename Type> void find_next_pair( Type *const, Type const &, int, int, int &, int & );
template <typename Type> void swap( Type *const, int const, int const );

template <typename Type>
void quick_sort( Type *const array, int const n, int const use_insert = 72 ) {
    quick_sort_recursive( array, 0, n - 1, use_insert );
}

template <typename Type>
void quick_sort_recursive( Type *const array, int const a, int const c, int const use_insert ) {
    if ( c - a < use_insert ) {
        pointer::insertion_sort_internal( array + a, array + c );
        return;
    }

    int b = (a + c)/2;
    Type pivot = array[b];
    array[b] = array[c];

    int lower = a;
    int upper = c - 1;

    find_next_pair( array, pivot, a, c, lower, upper );

    while ( upper >= lower ) {
        swap( array, lower, upper );
        find_next_pair( array, pivot, a, c, lower, upper );
    }

    array[c] = array[lower];
    array[lower] = pivot;

    quick_sort_recursive( array, a, upper, use_insert );
    quick_sort_recursive( array, lower + 1, c, use_insert );
}

template <typename Type>
inline void find_next_pair( Type *const array, Type const &pivot, int a, int c, int &lower, int &upper ) {
    while ( lower < c && array[lower] < pivot ) {
        ++lower;
    }

    while ( upper >= a && array[upper] > pivot ) {
        --upper;
    }
}

template <typename Type>
void swap( Type *const array, int const a, int const b ) {
    Type tmp = array[a];
    array[a] = array[b];
    array[b] = tmp;
}

Implementation on Arrays

This implementation:

• Choses the median-of-three as the pivot.

Note that by chosing the median-of-three, there is guaranteed to be one entry smaller than the pivot and one entery greater than the pivot. This removes some unnecessary checks used in the basic version.

Because the algorithm is faster, the cut-off for using insertion sort is significantly smaller.

Implementation using Pointers

This implementation:

• Uses pointers to walk through the arrays.

This significantly reduces the run time of most of the routines.

Use of Cut-Offs for Insertion Sort

Figure 1 shows the run times of various versions of cut-offs for using insertion sort. The three graphs are basic (red), array-based (black), and pointer-based (blue).

Figure 1. The run times of sorting 100 million objects for the three implementations with various insertion-sort cut-offs.