Improving performance when sorting array of structs by multiple fields

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

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 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 yFirstComparer = KeyComparer.OrderBy(c => c.Y)
    .ThenBy(c => c.CubeType).ThenBy(c => c.LightLevel).ThenBy(c => c.X).ThenBy(c => c.Z);

StackExchange Code Review Q#34023, answer score: 8