Merge Sort

Pros:  Very fast, one of the fastest.  n lg n sort.
Stable.

Cons:  Requires recursion, so can't be easily implemented in older languages.
You need space for a copy of the way for temporary storage.

Shell Sort, probably obsolete now.  But it was really good in the olden days (like the 1970's).  Has nothing to do with shells.  Shell was the name of the guy who came up with it.

You break the array up into increasingly smaller intervals, and sort each interval with a linear insertion sort.

Q W E R T Y U I O P

There are 10 items on the list, so I am going to use intervals of
9, 8, 6, 4, 3, 2, 1.
A lot of people have theories as to the best set of intervals.  So, not everyone chooses this set.  However, if the intervals ALL have no prime factors other than 2 or 3, the insertion sort part works much more smoothly.

We start by looking at the elements that are 9 apart.

Q W E R T Y U I O P
^                 ^

P W E R T Y U I O Q

Now let's look at the ones that are 8 apart.

P W E R T Y U I O Q
^               ^

O W E R T Y U I P Q
  ^               ^

O Q E R T Y U I P W

Now let's look at the ones that are 6 apart.

O Q E R T Y U I P W
^           ^

O Q E R T Y U I P W
  ^           ^

O I E R T Y U Q P W
    ^           ^

O I E R T Y U Q P W
      ^           ^

Now let's look at the ones that are 4 apart

O I E R T Y U Q P W
      1 2 3   1 2 3

O I E Q P W U R T Y

Now let's look at the ones that are 3 apart

O I E Q P W U R T Y
          1     1

O I E Q P T U R W Y

Now let's look at the ones that are 2 apart

O I E Q P T U R W Y
1   1     2   2

E I O Q P R U T W Y

Now let's look at the ones that are 1 apart

E I O Q P R U T W Y
      1 1   2 2

E I O P Q R T U W Y

Ta-da!

But if the intervals contain no prime factors other than 2 or 3, then at each pass, no element gets swapped more than once.

Linear insertion sort:

D C B A

C D B A

C B D A

B C D A

B C A D

B A C D

A B C D

However, in the shell sort, if the intervals contain no prime factors other than 2 or 3, the linear insertion never swaps the same element twice.

There are about lg^2 (n) numbers less than n whose only prime factors are 2 and 3.  Since a pass looks at all n elements in the array, and there are about lg^2 (n) passes, this runs in n lg^2 (n) time which is slower than n lg n time, but MUCH faster than n^2 time, like the Bubble Sort or the Linear Insertion Sort.

Now what if we made fewer passes?  If we make fewer passes, we are no longer guaranteed that each elements swaps only once, so each pass takes a little bit longer.  It's going to be slower than n lg n, and there are some crazy unlucky original permutations that will take about n^2 time to sort.  Some people prefer the 2-3 version of Shell Sort because it is guaranteed to be no slower than n lg^2 n, but other people prefer other choices for the intervals because in practice they can get faster times with them.

Shell Sort:

Pros:

Still runs reasonably fast
Does not use recursion.
Does not use much extra storage space.
Code is simple and easy to understand.

Cons:

Significantly slower than n lg n sorts like Merge Sort.
Not stable.

What does it mean for a sort to be stable?

If you are sorting records with IDENTICAL key fields, in the final sorted list, the records with identical key fields should be in same relative order in the sorted list as they were in the original list.

Action Comics / Superman
Detective Comics / Batman
Action Comics / Lois Lane

Action Comics / Superman
Action Comics / Lois Lane
Detective Comics / Batman

The Merge Sort is stable.  Superman is guaranteed to come before Lois Lane.

The Shell Sort is not stable.  While both Action Comics will appear before Detective Comics, Superman is not guaranteed to come before Lois Lane.  It might.  It might not.