Most efficient way to sort a circular buffer

Question

I've implemented a circular buffer using a fixed-length array. In order to point to the start of valid data, I use an index (_startIndex). Similarly, in order to point to the end of valid data, I use another index (_endIndex). Below is an example.

  9   8   7   6   5   4   3   2   1   0   <-- array indices
  3   2   1   0                   5   4   <-- buffer indices
-----------------------------------------
|   |   |   |   |   |   |   |   |   |   |
-----------------------------------------
              ^                   ^
             _startIndex         _endIndex

Now I need to rearrange the elements of this buffer: the smallest element should be moved to position 0 of the buffer, while the largest element should be moved to position 5 of the buffer.

My idea is based on the following method.

int GetArrayIndex(int bufferIndex)
{
    return (_startIndex + bufferIndex) % LENGTH;
    // LENGTH is the length of the array
}

In this way, the sorting algorithm could read the buffer sequentially, using the above method, without therefore having to be aware that the buffer consists of two non-contiguous portions of the same array. Are there better ways to sort a circular buffer?

Answer 1

If you want to do an in-place sort, then you should compress the buffer first. That is, make it one contiguous block from index 0 to index 5.

Then you can call the Array.Sort(T[], index, length) overload to sort that portion of the array.

You can move the items with a single operation, once you figure out what to move, and where.

There are three cases:

1. start_index == 0: No movement needed

2. start_index < end_index: Number of items to move is (end_index - start_index + 1). Move items from start_index through end_index to positions '0' through 'count-1'

3. start_index > end_index: There is a "hole" in the array (as you've shown). You need to move items from start_index through the end of the array to position array.length - start_index - count.

Once you figure out the source and destination positions, you can call Buffer.BlockCopy to move the items.

I should note that, after the move and sort is done, you can set start_index to 0, and end_index to count-1. Or, if you really want the buffer to be in the same state it was in before (just with re-ordered items), you can move things back using the same kind of logic I described above. Why you'd want to do that is unclear.