qsort.cs

        // https://github.com/mono/mono/blob/master/mono/eglib/gqsort.c

        /*
        * QuickSort
        *
        * Author: Jeffrey Stedfast <fejj@novell.com>
        *
        * (C) 2011 Novell, Inc.
        *
        * Permission is hereby granted, free of charge, to any person obtaining
        * a copy of this software and associated documentation files (the
        * "Software"), to deal in the Software without restriction, including
        * without limitation the rights to use, copy, modify, merge, publish,
        * distribute, sublicense, and/or sell copies of the Software, and to
        * permit persons to whom the Software is furnished to do so, subject to
        * the following conditions:
        *
        * The above copyright notice and this permission notice shall be
        * included in all copies or substantial portions of the Software.
        *
        * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
        * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
        * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
        * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
        * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
        * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
        * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
        */

        private unsafe struct QSortStack {
            public int* pData;
            public int count;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static unsafe void StackPush (ref QSortStack *sp, int* pData, int count) {
            sp->pData = pData;
            sp->count = count;
            sp++;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static unsafe void StackPop (ref QSortStack *sp, out int* pData, out int count) {
            sp--;
            pData = sp->pData;
            count = sp->count;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static unsafe int Compare (int* lhs, int* rhs) {
            return *rhs - *lhs;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static unsafe void Swap (int* lhs, int* rhs) {
            var temp = *lhs;
            *lhs = *rhs;
            *rhs = temp;
        }

        const int QSortStackSize = 8 * sizeof(int);
        const int QSortMaxThreshold = 7;

        public static unsafe void QuickSort (
            int* pData, int count
        ) {
            var stack = stackalloc QSortStack[QSortStackSize];
            var sp = stack;
            StackPush(ref sp, pData, count);

            int* lo, mid, hi, i, k;
            int n, n1, n2;

            do {
                StackPop(ref sp, out lo, out n);

                hi = lo + (n - 1);
        
                if (n < QSortMaxThreshold) {
                    /* switch to insertion sort */
                    for (i = lo + 1; i <= hi; i += 1)
                        for (k = i; k > lo && (*(k - 1) - *k) > 0; k -= 1)
                            Swap (k - 1, k);
            
                    continue;
                }
        
                /* calculate the middle element */
                mid = lo + (n / 2);
        
                /* once we re-order the lo, mid, and hi elements to be in
                    * ascending order, we'll use mid as our pivot. */
                if ((*mid - *lo) < 0) {
                    Swap (mid, lo);
                }
        
                if ((*hi - *mid) < 0) {
                    Swap (mid, hi);
                    if (Compare (mid, lo) < 0) {
                        Swap (mid, lo);
                    }
                }
        
                /* since we've already guaranteed that lo <= mid and mid <= hi,
                    * we can skip comparing them again */
                i = lo + 1;
                k = hi - 1;
        
                do {
                    /* find the first element with a value > pivot value */
                    while (i < k && (*i - *mid) <= 0)
                        i += 1;
            
                    /* find the last element with a value <= pivot value */
                    while (k >= i && (*mid - *k) < 0)
                        k -= 1;
            
                    if (k <= i)
                        break;
            
                    Swap (i, k);
            
                    /* make sure we keep track of our pivot element */
                    if (mid == i) {
                        mid = k;
                    } else if (mid == k) {
                        mid = i;
                    }
            
                    i += 1;
                    k -= 1;
                } while (true);
        
                if (k != mid) {
                    /* swap the pivot with the last element in the first partition */
                    Swap (mid, k);
                }
        
                /* calculate segment sizes */
                n2 = (int)(hi - k);
                n1 = (int)(k - lo);
        
                /* push our partitions onto the stack, largest first
                    * (to make sure we don't run out of stack space) */
                if (n2 > n1) {
                    if (n2 > 1) StackPush(ref sp, k + 1, n2);
                    if (n1 > 1) StackPush(ref sp, lo, n1);
                } else {
                    if (n1 > 1) StackPush(ref sp, lo, n1);
                    if (n2 > 1) StackPush(ref sp, k + 1, n2);
                }
            } while (sp > stack);
        }