 Shell Sort  The shell sort is named after its inventor D. L. Shell.  Instead of comparing adjacent elements, like the bubble sort, the shell sort repeatedly compares elements that are a certain distance away from each other (d represents this distance).  The value of d starts out as half the input size and is halved after each pass through the array.  The elements are compared and swapped when needed.  The equation  d = (N + 1) / 2  is used.  Notice that only integer values are used for d since integer division is occurring.

Let's look at our same list of values for descending order with the shell sort.  Remember, a "pass" is defined as one full trip through the array comparing and if necessary, swapping elements.
 Array at beginning: 84 69 76 86 94 91 d After Pass #1: 86 94 91 84 69 76 3 After Pass #2: 91 94 86 84 69 76 2 After Pass #3: 94 91 86 84 76 69 1 After Pass #4 (done): 94 91 86 84 76 69 1

First Pass:  d = (6 + 1) / 2 = 3.  Compare 1st and 4th , 2nd and 5th, and 3rd and 6th items since they are  3 positions away from each other))
Second Pass:  value for d is halved  d = (3 + 1) / 2 = 2.  Compare items two places away such as 1st and 3rd ……
Third Pass:  value for d is halved  d = (2 + 1) / 2 = 1.  Compare items one place away such as 1st and 2nd …..
Last Pass:  sort continues until d = 1 and the pass occurs without any swaps.

This sorting process, with its comparison model, is an efficient sorting algorithm.

//Shell Sort Function for Descending Order
void ShellSort( apvector <int> &num)
{
int i, temp, flag = 1, numLength = num.length( );
int d = numLength;
while( flag || (d > 1))      // boolean flag (true when not equal to 0)
{
flag = 0;           // reset flag to 0 to check for future swaps
d = (d+1) / 2;
for (i = 0; i < (numLength - d); i++)
{
if (num[i + d] > num[i])
{
temp = num[i + d];      // swap positions i+d and i
num[i + d] = num[i];
num[i] = temp;
flag = 1;                  // tells swap has occurred
}
}
}
return;
} 