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

Enhanced Implementation on Arrays

This implementation:

• Avoids unnecessary swaps.

Enhanced Implementation using Pointers

This implementation:

• Uses pointers to walk through the arrays.