Stable sort:  A sort that preserves the order of elements with identical keys.  If two elements have the same key, the one that appears first, second, etc., in the sorted list is the one that appears first, second, etc., in the unsorted list.

The easiest way to make any sort stable is to remove the possibility of duplicate keys.

Wrong way to do it:  Just use a regular shell sort and then after the sort is done, go through the list again and reorder the identical keys based on the tag field.

Correct way:  sort it only once using the Shell Sort.  When you compare two keys, and one comes before the other, just do what the Shell Sort normally does, swap them or not swap them.  If the keys are identical, THEN, BEFORE YOU MOVE ON, look at the tag fields, one tag field will come before the other, swap or don't swap based on that.

Then when the Shell Sort is done, it will be sorted and stable.

A C C E H L O O T
6 0 3 8 1 5 2 4 7

100: 96 81 72 64 54 48 36 32 27 24 18 16 12 9 8 6 4 3 2: 1

100: 50 25 12 6 3 : 1

Fewer passes means that each pass deals with more out of order elements.
The (2,3) Shell Sort guarantees that on any given pass no element will be moved more than one.  But other versions of the Shell Sort cannot make that guarantee.

The (2,3) Shell Sort is guaranteed to run in n lg^2 n time.  But the other versions of Shell Sort have no such guarantee.  The halving Shell Sort could run in n^2 time (like Bubble Sort).

1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16

16: 8 4 2 : 1

100 elements

1 4 13 40  based on multiples of 3.

100:  40 13 4 : 1

Variations on Sorting:

Stable Sort:  when you want to keep identical keys in order

Partial Sorting:  Say you have a million elements, but you only need the top 50.  So how can you find the top 50 without sorting all million of them?

We have an array of size 50.  We can through the million elements and we see if any of them are better than the fifty best we've seen, if so, we add it to the array, and throw out the worst one in that array, keeping it at 50.  When we're all done, we have the top 50 in that array.