Code:
/*
ShellSort is very fast at short arrays, but QuickSort's segregation helps multi-CPU with long arrays.
Included are gaps up to C's max integer = 2^31 - 1, subsequent being commented out.
From http://en.wikipedia.org/wiki/Shellsort
> Gonnet and Baeza-Yates observed that Shellsort makes the fewest comparisons on average when the ratios of successive
> gaps are roughly equal to 2.2. This is why their sequence with ratio 2.2 and Tokuda's sequence with ratio 2.25
> prove efficient. However, it is not known why this is so. Sedgewick recommends using gaps which have low greatest
> common divisors or are pairwise coprime.
So, start 1, 3, then closest to immediately previous * Sqrt5 that is coprime to all smaller
==> ratios tend to ~=2.236.
Gap >=83 ==> ratio within -0.0242% to +1.7% of Sqrt5.
*/
static double tolerance;
inline _Bool rhombiiGt(const Rhombus* const rhP0, const Rhombus* const rhP1)
{
// [blah, using tolerance]
} // rhombiiGt
static int* ShellSortGaps;
void ShellSort(struct Rhombus *rhombii, int n, const double tol)
{
int intervalNum, interval, i, j;
struct Rhombus rh;
tolerance = tol;
if( NULL == ShellSortGaps )
{
ShellSortGaps = malloc( sizeof(int) * 27 );
ShellSortGaps[ 0] = 1 ;
ShellSortGaps[ 1] = 3 ;
ShellSortGaps[ 2] = 7 ;
ShellSortGaps[ 3] = 16 ;
ShellSortGaps[ 4] = 37 ;
ShellSortGaps[ 5] = 83 ;
ShellSortGaps[ 6] = 187 ;
ShellSortGaps[ 7] = 419 ;
ShellSortGaps[ 8] = 937 ;
ShellSortGaps[ 9] = 2099 ;
ShellSortGaps[10] = 4693 ;
ShellSortGaps[11] = 10499 ;
ShellSortGaps[12] = 23479 ;
ShellSortGaps[13] = 52501 ;
ShellSortGaps[14] = 117391 ;
ShellSortGaps[15] = 262495 ;
ShellSortGaps[16] = 586961 ;
ShellSortGaps[17] = 1312481 ;
ShellSortGaps[18] = 2934793 ;
ShellSortGaps[19] = 6562397 ;
ShellSortGaps[20] = 14673961 ;
ShellSortGaps[21] = 32811973 ;
ShellSortGaps[22] = 73369801 ;
ShellSortGaps[23] = 164059859 ;
ShellSortGaps[24] = 366848983 ;
ShellSortGaps[25] = 820299269 ;
ShellSortGaps[26] = 1834244921 ; // Below 2^31 ~= 2 billion
/*
4101496331, 9171224603, 20507481647, 45856123009, 102537408229, 229280615033, 512687041133, 1146403075157, 2563435205663,
5732015375783, 12817176028331, 28660076878933, 64085880141667, 143300384394667, 320429400708323, 716501921973329,
1602147003541613, 3582509609866643, 8010735017708063, // Excel's integers misbehave after 1 quadrillion
17912548049333207, 40053675088540303, 89562740246666023, 200268375442701509, 447813701233330109,
1001341877213507537, 2239068506166650537, 5006709386067537661, 11195342530833252689 // Below 2^64 ~= 18 quintillion
*/
} // NULL == ShellSortGaps
for(intervalNum = 0; intervalNum < 27 && ShellSortGaps[intervalNum] <= n ; intervalNum++)
;
intervalNum--;
// Based on Algorithms in C (1990), Robert Segdewick, p109
for( ; intervalNum >= 0 ; intervalNum-- )
{
interval = ShellSortGaps[intervalNum];
for(i = interval+1 ; i <= n ; i+= interval)
{
rh = rhombii[i];
j = i;
while( j > interval && rhombiiGt(rhombii + (j - interval), &rh) )
{
rhombii[j] = rhombii[j - interval];
j -= interval;
} // j loop
rhombii[j] = rh;
} // i loop
} // intervalNum,interval loop
} // ShellSort
The population of the array is nasty nasty! Is there en elegant way to define, and allocate the memory for, the 
