Why doesn't the distribution of inversions matter in insertion sort?

Question

According to Robert Sedwick, shell sort (supposed to run faster than insertion sort) tries to minimize the inversion distance with different h-sortings. In a way , this h-sorting procedure makes file nearly sorted hence rearrange inversion distribution in more symmetric way.

Then how can one say (according to book), insertion sort run time depends on number of inversions & not on their distribution manner?

Answer 1

In insertion sort, every swap that's made reduces the number of inversions by exactly one. Imagine, for example, that we're about to swap two adjacent elements B and A in insertion sort. Right before the swap, the array looks something like this:

   +--------------+---+---+------------+
   |    before    | B | A |    after   |
   +--------------+---+---+------------+

And, right afterwards, it looks like this:

   +--------------+---+---+------------+
   |    before    | A | B |    after   |
   +--------------+---+---+------------+

Now, think about the inversions in the array. Any inversion purely in "before" or "after" is still there. Every inversion from "before" into "after" is still there, as are inversions from "before" into A, "before" into B, A into "after," and B into "after." The only inversion that's gone is the specific inversion pair (A, B). Consequently, the number of swaps in insertion sort is exactly equal to the number of inversions, since each inversion requires one swap and the algorithm stops when no inversions are left. Notice that it's just the total number of inversions that matters, not where they are.

On the other hand, this is not true about shellsort. Suppose in shellsort that we swap elements B and A, which are out of place but not adjacent. Schematically, right before the swap we have something like this:

   +--------------+---+----------+---+------------+
   |    before    | B |  middle  | A |    after   |
   +--------------+---+----------+---+------------+

And we end with this:

   +--------------+---+----------+---+------------+
   |    before    | A |  middle  | B |    after   |
   +--------------+---+----------+---+------------+

The inversion (B, A) is now gone, but it's also quite possible that even more inversions were eliminated with this step. For example, suppose there are a bunch of elements in "middle" that are less than B. That single swap would then eliminate all of them at the same time.

Because each swap in shellsort can potentially eliminate multiple inversions, the actual locations of those inversions does actually matter for the runtime, not just their position.

Answer 2

Not an answer per se: shell sort actually does require fewer comparisons on average than insertion sort and possibly all other sort algorithms PROVIDED you supply it with the correct gap sequence that, in turn, is a function of n (the number of elements to be sorted). There is probably just one (unique) optimal gap sequence for every n.

Defining F(n) is, of course, the tricky part!