I am developing a game in Unity, c#. I have a large Vector3 list of 16k elements that has holds x position, y for dic key and z position.

The list gets sorted very often but only 2750 of that list gets sorted and the rest remains unsorted.

Right now I am using linq for a quickstort with orderby: list = list.OrderBy(x => x).ToList
But it is not the right sort algorithm for my case.

I have no idea how to implement an Insertion sort for a Cector3 list. Just did it with simple arrays. Is there maybe an Insertion sort (ascending and descending) for Vector3 list already in linq?

CodePudding user response：

Well turns out insertion sort is worse.

Thats how I wrote it:

    static void sortVec3Array(Vector3[] arrayToSort, int startAt, int stopAt)
{
    int i, j;
    for (i = startAt 1; i < stopAt; i  )
    {
        float item = arrayToSort[i].x;
        int ins = 0;
        for (j = i - 1; j >= 0 && ins != 1;)
        {
            if (item < arrayToSort[j].x)
            {
                arrayToSort[j   1].x = arrayToSort[j].x;
                j--;
                arrayToSort[j   1].x = item;
            }
            else ins = 1;
        }
    }
}

CodePudding user response：

Well came across Tim Sort which is kinda what I need.

I implemented it and it works like a charm. Ms is like 1.9 which is 3 times faster than the .Orderby algorithm and now useable for me.