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 500 thousand in 213 seconds, the enhanced array-based implementation sorts the same list in 79 seconds, and the pointer-based implementation sorts the list in 52 seconds.

Pseudo Code

To insert-sort an array of size n:
	Starting with a array if size 1
	Continue inserting the next object into the array until
	we create an array of size n.
end

Basic Implementation

template <typename Type> void insertion_sort_internal( Type *const, int const, int const );
template <typename Type> void swap( Type *const, int, int );

template <typename Type>
void insertion_sort( Type *const array, const  int n ) {
    insertion_sort_internal( array, 0, n - 1 );
}

template <typename Type>
void insertion_sort_internal( Type *const array, int const a, int const b ) {
    for ( int i = a + 1; i <= b; ++i ) {
        for ( int j = i - 1; j >= a; --j ) {
            if ( array[j] > array[j + 1] ) {
                swap( array, j, j + 1 );
            } else {
                break;
            }
        }
    }
}

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

Enhanced Implementation on Arrays

This implementation:

• Avoids unnecessary swaps.

template <typename Type>
void insertion_sort( Type *const array, const  int n ) {
    insertion_sort_internal( array, 0, n - 1 );
}

template <typename Type>
void insertion_sort_internal( Type *const array, int const a, int const b ) {
    for ( int i = a + 1; i <= b; ++i ) {
        Type tmp = array[i];

        for ( int j = i - 1; j >= a; --j ) {
            if ( array[j] > tmp ) {
                array[j + 1] = array[j];
            } else {
                array[j + 1] = tmp;
                goto object_placed;
            }
        }

        array[a] = tmp;

        object_placed: ;
    }
}

Enhanced Implementation using Pointers

This implementation:

• Uses pointers to walk through the arrays.

template <typename Type>
void insertion_sort( Type *const array,const  int n ) {
        insertion_sort_internal( array, array + n - 1 );
}

template <typename Type>
void insertion_sort_internal( Type *const first, Type *const last ) {
    for ( Type *forward = first + 1; forward <= last; ++forward ) {
        Type tmp = *forward;

        for ( Type *back_0 = forward - 1, *back_1 = forward; back_0 >= first; ) {
            if ( *back_0 > tmp ) {
                *(back_1--) = *(back_0--);
            } else {
                *back_1 = tmp;
                goto object_placed;
            }
        }

        *first = tmp;

        object_placed: ;
    }
}