SHELL SORT

Shell Sort was invented by a guy named Shell.  It has nothing to do with shells.

The Shell Sort is based the repeated use of Insertion Sort over small lists and larger partially-sorted lists.

INSERTION SORT

Q W E R T
  ^  Is the W OK where it is or can it be pushed to the left?

Q W E R T
    ^    Can we push the E to the left?

Q E W R T
  ^ Can we still push it to the left?

E Q W R T
      ^  Can we push it to the left?

E Q R W T
    ^ Can we still push it to the left?  No.

E Q R W T
        ^ Can we push it to the left?

E Q R T W
      ^ Can we still push it to the left?  No.

Our sorted list is E Q R T W.

The insertion sort runs is n^2 time, so it should never be used by sane individuals.  However, it's about the best of the bad sorts.  In fact, of all sorts based around the comparing of adjacent items in the array, Insertion Sort is the best.


SHELL SORT:

If we have n items in the array, we come up with a list of numbers less than n and greater than 1 (the exact list is disputed as to what it ought to be), and insertion-sort items that are that many apart from each other.  Then finally insertion-sort the list, the list is then sorted.

Q W E R T Y U I O P       list:5,3

Lists that are 5-apart from each other.

Q Y  Insertion sort:  Y can't be moved, so it's QY
W U  U can be moved:  UW
E I  I can't be moved.  EI
R O  O can be moved:  OR
T P  P can be moved:  PT

QUEOPYWIRT

Lists that are 3-apart from each other

QOWT   OQWT  OQTW
UPI    PUI   PIU    IPU
EYR    ERY

OIEQPRTUYW

Now we insertion sort the whole thing

IOEQPRTUYW
IEOQPRTUYW
EIOQPRTUYW
EIOPQRTUYW
EIOPQRTUWY

Insertion ran a lot faster on this partially sorted list than it would have on a random unsorted list.

What should the ideal choice of list lengths between and 1 be????  People have different ideas.

Advantages:  Sort in place; you do not need another copy of the array.
Does not require recursion.  Uses simple loops only.
Code is short.

While the selection of sublists lengths is still open to debate, one popular view among theorists (as opposed to scholars on the practical end of things) is that the sublists should be those list lengths who prime factors are nothing other than 2 or 3.

10:  9, 8, 6, 4, 3, 2

Obvious downside:  There are a lot of numbers with no prime factor beyond two or three and this gives us a lot of sublists to check.

Not-so-obvious advantage:  let's find out.

Q W E R T Y U I O P

9-apart

QP  ==> PQ
W
E
R
T
Y
U
I
O

PWERTYUIOQ

PO  OP
WQ  QW
E
R
T
Y
U
I

OQERTYUIPW

6-apart

OU  OU
QI  IQ
EP  EP
RW  RW
T
Y

OIERTYUQPW

4-apart

OTP  => OPT
IYW  => IWY
EU   => EU
RQ   => QR

OIEQPWURTY

3-apart

OQUY
IPR
EWT

OIEQPWURTY

2-apart

OEPUT => EOPTU
IQWRY => IQRWY

EIOQPRTWUY

Insertion sort the whole thing

EIOPQRTUWY

The upside of this longer approach is that no element, at any of these sorts moves more than one position.