Improving performance when sorting array of structs by multiple fields

Question

I have an array of a struct containing 5 byte values. I need to sort this array by each value in a different order depending on the situation. These arrays are sometimes quite small (10-30 elements), sometimes quite large (1024-16384).

Below is the code I'm using. The reason this has become a bottleneck for me is due to having to make it an array again which reallocates memory for it if I understand correctly (for both the sort and turning it back to an array). My desire is to sort the array the way I want (which can be one of the 3 below situations) without having to do something like ToArray and instead populate the array that exists.

I may be entirely wrong about sorting like this or my analysis of the problem, which is why I'm here. If anyone can point me to a better way to do this, please let me know. This program needs to be able to call this routine hundreds (sometimes thousands) of times per second.

public enum eCubeType : byte {
    Air = 0,
    Dirt = 1
}

public struct strCubeFace {
    public byte X, Y, Z, LightLevel;
    public eCubeType CubeType;
}

Function call snippet including array sorting code:

        if (iSide == 0 || iSide == 1) {
            Faces = Faces.OrderBy(c => c.Y).ThenBy(c => c.CubeType).ThenBy(c => c.LightLevel).ThenBy(c => c.X).ThenBy(c => c.Z).ToArray();
            SmartMesh0();
        }
        if (iSide == 2 || iSide == 3) {
            Faces = Faces.OrderBy(c => c.Z).ThenBy(c => c.CubeType).ThenBy(c => c.LightLevel).ThenBy(c => c.X).ThenBy(c => c.Y).ToArray();
            //SmartMesh1();
        }
        if (iSide == 4 || iSide == 5) {
            Faces = Faces.OrderBy(c => c.X).ThenBy(c => c.CubeType).ThenBy(c => c.LightLevel).ThenBy(c => c.Y).ThenBy(c => c.Z).ToArray();
            //SmartMesh2();
        }

Edit for @svick or anyone else wanting to know more details:

This is in regards to a 3D procedural map generator that expands as the player moves outwards. The terrain is geometrically similar to that of Infiniminer or Minecraft. This lends itself well to combining like faces of the cube based terrain to lower vertices by 50% or higher (usually higher).

After generating the points I need to represent each cube, it's light level, and so on; I then iterate over every solid block that is adjacent to transparent/translucent blocks to create the strCubeFace structure I use to represent individual faces.

Unless I am simply doing this whole process in a very "bad" way for performance, I need to sort 6 of these arrays per chunk (grouping of 32x256x32 cubes), one for each face. It is indeed always a different array each time it is needed to be sorted. It doesn't necessarily need to be an array, but as I already know the total number of cubes adjacent to transparent/translucent blocks, setting up a simple array of the max size made the most sense to me (once the array is populated, if the number of faces in each specific array is larger than the array's length, I simply re-size the array down prior to the sort). It is my belief that most other collection storage techniques would incur a higher processing penalty or a higher memory storage penalty.

The only reason I am sorting these to begin with, which is probably most important to know/understand, is so that I can iterate over the sorted array of faces to very quickly/easily create the vertices necessary to combine like faces.

Sorry for rambling so much, but this is a rather big project and I'm not so good at condensing down my reasoning for any of these things without nearly writing a paper on the subject since it's all so intertwined. I'd nearly just post the whole project for review, but that would seem inappropriate (that and my code is borderline illegible at times as I'm currently just a hobbyist).

Answer 1

If your analysis is correct and the slowdown is really cased by the copying, then you could avoid that by using Array.Sort(), which directly sorts the array you have.

Though Array.Sort() isn't as convenient as OrderBy() combined with ThenBy(), you will have to create an IComparer or Comparison for each of the possible sort orders. It could look something like this:

Comparison<eCubeType> yFirstComparison = (c1, c2) =>
{
    int result = c1.Y.CompareTo(c2.Y);
    if (result != 0)
        return result;

    // ...

    return c1.Z.CompareTo(c2.Z);
}

If you don't like to do this manually you can use NList (the project site seems to be down at the moment):

IComparer<eCubeType> yFirstComparer = KeyComparer<eCubeType>.OrderBy(c => c.Y)
    .ThenBy(c => c.CubeType).ThenBy(c => c.LightLevel).ThenBy(c => c.X).ThenBy(c => c.Z);