amylib

Chunk Sort

This is a variation of insertion sort that looks ahead for swaps to do in advance. Somehow this is better than O(n²) for random data. It overtakes straight insertion sort at about n=400 on my computer, and is about five to ten times faster at n=8000. Like insertion sort, it is O(n) for already sorted data.

The procedure for sorting an array A is as follows:

Find the first element A[i] such that A[i+1] < A[i]
Find the next A[j] such that A[j] > A[i]. The range i <= x < j is called a "chunk".
Move j left 1 place, to point to the last element in the chunk.
If A[j] < A[i], swap them and move both i and j left by one place. Otherwise save the position j, skip over A[j] and only move j left by one place.
When the size of the chunk reaches 1, simply insert the last element as in insertion sort.
Set i=(last saved position)+1 and loop until i>length(A).

Note that i and j don't mean the same things in the code as they do in the above description, just to confuse you.


class ChunkSort
{
   std::vector<int>& dataIn;
   int* data;
   int length;

public:
   ChunkSort ( std::vector<int>& toSort )
    : dataIn  ( toSort),
      data    (&toSort.front()),
      length  ( toSort.size ())
   {
      int i(0);
      int j(0);
      while (i < length)
      {
         if (++i==length || data[j] < data[i])
         {
            if (i>j+1)
            {
               int k(i-1);
               for (; k > j+1; --k)
               {
                  if (j<0)
                  {
                     i=0;
                     break;
                  }
                  else if (data[k] < data[j])
                  {
                     int temp(data[k]);
                     data[k]=data[j];
                     data[j]=temp;
                     --j;
                  }
                  else
                  {
                     i=j+1;
                  }
               }
               // insert the final element
               int temp = data[k];
               for (; (k > 0) && (temp < data[k-1]); --k)
               {
                  data[k] = data[k-1];
               }
            }
            j=i;
         }
      }
   }
};

And here are my sorting bees to demonstrate it:

amy 17.6.2011