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: ;
}
}