

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 Method for Descending Order
public static void ShellSort( int [ ] num)
{
int i, temp;
boolean flag = true;
int d = num.length;
while( flag  (d > 1)) // boolean flag set to true)
{
flag = false; // reset flag to false to check for future swaps
d = (d+1) / 2;
for (i = 0; i < (num.length  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 = true; // tells swap has occurred
}
}
}
}
