Shellsort

The game is different whether we consider external data structures—that live partially or totally on disk or over the network—or internal data structures residing entirely in local memory. For one thing, none of the courses I had on data structures I had really prepared me to deal adequately with (large) external data structures; it was always assumed that the computer’s memory was somehow spacious enough to hold whatever data you needed.

However, when you’re dealing with files, you can’t really assume that you can access random locations to read, write, or exchange data at low cost, and you have to rethink your algorithms (or change plans altogether) to take the cost of slow external media into account. Sometimes an algorithm that doesn’t look all that useful in main memory suddenly makes more sense in external memory because of the way it scans its data. One of these algorithms is the Shellsort.

No, Shellsort didn’t get its name from some crustacean/molluscean metaphor for sorting, but from Donald L. Shell, its inventor. Shellsort was published in 1959, [1], about two years before Hoare‘s Quicksort [2].

Shellsort is an extension of the infamous Bubblesort but instead of comparing and exchanging, if need be, only immediately neighboring cells, it relies on an increment sequence (or gap sequence) to compare-exchange cells that are further apart and eventually sort the array. The increment sequence is a sequence that starts mandatorily with 1 and is strictly increasing. For example, is one such sequence, another, but would not be an acceptable sequence. There are sequences that are better than others, as we will see.

So let us continue with the description of the sorting procedure. The basic step of the algorithm is the same as with Bubblesort, that is, we scan the array from bottom to top and compare-exchange neighboring elements. With Bubblesort, we consider only immediately neighboring cells, t[i] and t[i+1], and we bubble through the array as many times as necessary, until we can scan the array without performing an exchange. That is, something like:

bool touched;
do
 {
  touched=false;
  for (int i=0;i<n-1;i++)
   if (t[i]>t[i+1])
    {
     std::swap(t[i],t[i+1]);
     touched=true;
    }
 } while (touched);
 

This sorting procedure is notoriously bad. If a cell contains a value that is very far from its final (sorted) position, you can do up to swaps before getting that value to the desired position. The total running time is , which is very far from the we know is optimal for comparison-based sorts.

Shellsort, while doing essentially the same thing, tries to move values around faster using the increment sequence. Instead of comparing only t[i] and t[i+1], it will compare t[i] and t[i+inc], for some value of inc. It repeats the main loop with inc until no more swaps are performed. With Bubblesort, that would mean we are done (because increments are 1 and now the array is completely sorted) but if we have an increment greater than 1, the array is in a semi-sorted state (in fact, it is inc-sorted). With Shellsort, if the increment is not already 1, we decrease it significantly—the best sequences are geometric-looking—and repeat the bubbling until, again, no swaps are performed. And we decrease the increment again, and bubble again, and repeat the whole process until the increment eventually reaches one. When the increment is 1, we do a last Bubblesort (but most elements are almost sorted already) and the algorithm terminates.

Code speaks, and the implementation (essentially the one presented in [3]) is as follows:

////////////////////////////////////////
//
// Shell Sort
// http://en.wikipedia.org/wiki/Shell_sort
//
template <typename T>
void shell_sort(T items[],
               size_t nb_items,
               const size_t increment_sequence[],

               uint64_t & scans, // performance counter 
               uint64_t & swaps  // performance counter
               )
 {
  scans=0;
  swaps=0;

  if (nb_items)
   {
    // points to the current 
    // increment in sequence
    //
    int inc_index=0; 

    // find the first increment
    // smaller than the array.
    //
    while (increment_sequence[inc_index]>nb_items) inc_index++;

    // perform shell sort
    //
    while (increment_sequence[inc_index])
     {
      bool touched;
      const size_t this_inc=increment_sequence[inc_index];

      do//while(touched)
       {
        touched=false;

        scans+=nb_items-this_inc;

        for (int i=this_inc; i < nb_items; i++)
         if (items[i]<items[i-this_inc])
          {
           std::swap(items[i],items[i-this_inc]);
           swaps++;
           touched=true;
          }
       } while (touched);

      inc_index++;
     } 
   }
}

A first guess for the sequence would be to use a power-of-two sequence or (Shell’s initial guess) the sequence , and successive divisions until one reaches one, but it turns out, counter-intuitively, that it’s not so good. Over the years, people came up with better and better sequences (assuming just uniform random numbers in an array) and derived all kind of bounds on the complexity of Shellsort given those sequences. One showed that Shellsort with one sequence was , and another that with a different sequence it could be made , and we’re still wondering how much better it could get [3].

For the purpose of demonstrating the influence of the increment sequence, we chose the following sequences:

• Sedgewick‘s A003462
• Sedgewick’s A036562
• Sedgewick’s (or Sedgewick-Incerpi) A036569,
• Pigeon’s A055875, that I submitted in august 2000,
• Pigeon’s A055876, that I also submitted in August 2000 (the best sequence for a while, at least as far as I know)
• Powers of 2, , that isn’t all that good,
• Powers of 2 minus 1, , that performs rather well,
• Fibonacci, A000045,
• Ciura’s A102549, the best known sequence so far, from 2001
• “Fat Fibonacci” A154393

The test arrays, increasingly larger (1000 to 10000, steps of 1000), are initialized with uniform random values in the range 0 to RAND_MAX, and each test is repeated 50 times, with different random values. However, the same random arrays are used for all tests; that is, it is the same initial buffers of size 1000 for all sequences so that the increment sequences are compared fairly on the same random data.

The first result concerns the number of scans, or compares, performed by Shellsort given an increment sequence.

You see that Ciura’s sequence A102549 is the sequence that asks for the least number of compares, followed by A055876. Fibonacci and powers of 2 perform the worst, again maybe counter-intuitively.

The picture is slightly different when we compare the number of swaps by sequence. The power of 2 sequence now doesn’t perform all that bad; there are worse sequences.

However, the best way to compare the performance of the sequences would be to use a combined cost model where reading and exchanging have different costs, one cost for reading an entry, and another to rewrite it; let us feign that comparing (two reads) and exchanging (two reads, two writes) cost the same. This yields the following graphic:

where the three best sequences are Segdewick’s (or Sedgewick-Incerpi) A036569, the sequence A055876, and Ciura’s A102549.

*
* *

The complexity analysis of Shellsort is far from trivial and Ciura [4] resorted to essentially an empirical method to derive his best sequences and conjectures that it might be optimal. Ten years ago, I must admit that I also took an educated guess and a bit of empirical evidence to propose A055876, but it turns out that this sequence isn’t all that bad either.

---

[1] D. L. Shell — A High-Speed Sorting Procedure — Comm. ACM, v2(7), (1959) p. 30–32

[2] C. A. R. Hoare — Quicksort — The Computer Journal, v5(1) (1962) p. 10–15

[3] R. Sedgewick — Analysis of Shellsort and Related Algorithms — 4th Annual European Symposium on Algorithms (1996) LNCS# 1136, p. 1–11

[4] M. Ciura — Best Increments for the Average Case of Shellsort — 13th Int. Symposium on Fundamentals of Computation (2001) LNCS# 2138, p. 106–117