How to sort a number sequence that wraps around

Question

I have a sequence of objects, that each have a sequence number that goes from 0 to ushort.MaxValue (0-65535). I have at max about 10 000 items in my sequence, so there should not be any duplicates, and the items are mostly sorted due to the way they are loaded. I only need to access the data sequentially, I don't need them in a list, if that can help. It is also something that is done quite frequently, so it cannot have a too high Big-O.

What is the best way to sort this list?

An example sequence could be (in this example, assume the sequence number is a single byte and wraps at 255):

240 241 242 243 244 250 251 245 246 248 247 249 252 253 0 1 2 254 255 3 4 5 6

The correct order would then be

240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 0 1 2 3 4 5 6 

I have a few different approaches, including making a array of ushort.MaxValue size, and just incrementing the position, but that seems like a very inefficient way, and I have some problems when the data I receive have a jump in sequence. However, it's O(1) in performance..

Another approach is to order the items normally, then find the split (6-240), and move the first items to the end. But I'm not sure if that is a good idea.

My third idea is to loop the sequence, until I find a wrong sequence number, look ahead until I find the correct one, and move it to its correct position. However, this can potentially be quite slow if there is a wrong sequence number early on.

Answer 1

Is this what you are looking for?

var groups = ints.GroupBy(x => x < 255 / 2)
     .OrderByDescending(list => list.ElementAt(0))
     .Select(x => x.OrderBy(u => u))
     .SelectMany(i => i).ToList(); 

Example In:

int[] ints = new int[] { 88, 89, 90, 91, 92, 0, 1, 2, 3, 92, 93, 94, 95, 96, 97, 4, 5, 6, 7, 8, 99, 100, 9, 10, 11, 12, 13 };

Out:

88 89 90 91 92 92 93 94 95 96 97 99 100 0 1 2 3 4 5 6 7 8 9 10 11 12 13

Answer 2

I realise this is an old question byte I also needed to do this and would have liked an answer so...

Use a SortedSet<FileData> with a custom comparer;

where FileData contains information about the files you are working with e.g.

struct FileData
{
    public ushort SequenceNumber;
    ...
}

internal class Sequencer : IComparer<FileData>
{
    public int Compare(FileData x, FileData y)
    {
        ushort comparer = (ushort)(x.SequenceNumber - y.SequenceNumber);
        if (comparer == 0) return 0;
        if (comparer < ushort.MaxValue / 2) return 1;
        return -1;
    }
}

As you read file information from disk add them to your SortedSet

When you read them out of the SortedSet they are now in the correct order

Note that the SortedSet uses a Red-Black Internally which should give you a nice balance between performance and memory

Insertion is O(log n)
Traversal is O(n)