What is the benefit of Shell Sort versus Insertion/Bubble Sort?

Question

My professor gave me the following definition of Shell Sort. I've included the Bubble and Insertion Sort algorithms as well.

What is the advantage of using Shell Sort vs just a regular Insertion Sort or Bubble Sort with gap=1? Eventually, the Shell Sort boils down to that anyway, right?

I'm not asking you to do my homework. I'm legitimately confused and want to understand what's going on.

Also, I've already visited Wikipedia and seen the Time Complexity table and I already know what they say. I'm looking for the why, not the what.

def shell(a, n):
    gap = n / 2

    while gap >= 1:
            insertion(a, n, gap) # or bubble
            gap /= 2

def bubble(a, n, gap=1):
    for i in range(n):
            for j in range(n-i-gap):
                    if a[j] > a[j+gap]:
                            swap(a, j, j+1)

def insertion(a, n, gap=1):
    for i in range(1,n):
            x = a[i]
            j = i-gap

            while j>=0 and  a[j]>x:
                    a[j+gap] = a[j]
                    j-=gap

            a[j+gap]=x

Answer 1

The logic of shell sort is to sort entries that are further away first. Given a partially sorted list you can in theory sort a lot faster than O(n^2). Also given a large unsorted array the probability that your final sorted position being far from your current position is high. So logically it makes sense to use a larger gap. But the main point of shell sorts is not really its performance, instead it is the simplicity of the algorithm and the low usage of stack memory.

Given that on average it does better than O(n^2) (depends of the gap sequence), small code sizes and stack usages it is very popular in embedded applications where memory constraints are a factor.

Answer 2

Shell sort allows swapping of indexes that are far apart, where bubble sort only swaps items that are adjacent.

The wikipedia entries on

• http://en.wikipedia.org/wiki/Shell_sort
• http://en.wikipedia.org/wiki/Insertion_sort
• http://en.wikipedia.org/wiki/Bubble_sort

cover the differences.

Edit:

Imagine that you've got a bunch of cards in your hand and the cards are almost in order, except the first and last are swapped. bubble sort would be a pain to do, because there'd be about 2n swaps, insertion sort would be better with n swaps, but shell sort could do it in 1. (the number of swaps varies based on algorithm implementation, this is just an example)