From 71bb64df713675bd40c62f3071a6d4cb86b3c94c Mon Sep 17 00:00:00 2001 From: Jeffrey Stedfast Date: Tue, 7 Aug 2012 12:17:16 -0400 Subject: [PATCH] [corlib] Fallback to Insertion Sort in the non-generic qsort() Many thanks to Martin Potter for taking the time to implement this, crossing it off of the long TODO list! --- mcs/class/corlib/System/Array.cs | 29 +++++++++++++++++++++++++++-- 1 file changed, 27 insertions(+), 2 deletions(-) diff --git a/mcs/class/corlib/System/Array.cs b/mcs/class/corlib/System/Array.cs index 5606a62501e..6d1ef1db194 100644 --- a/mcs/class/corlib/System/Array.cs +++ b/mcs/class/corlib/System/Array.cs @@ -1455,7 +1455,7 @@ namespace System private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer) { QSortStack[] stack = new QSortStack[32]; - //const int QSORT_THRESHOLD = 7; + const int QSORT_THRESHOLD = 7; int high, low, mid, i, k; object key, hi, lo; IComparable cmp; @@ -1471,7 +1471,32 @@ namespace System high = stack[sp].high; low = stack[sp].low; - // TODO: implement InsertionSort when QSORT_THRESHOLD reached + if ((low + QSORT_THRESHOLD) > high) { + // switch to insertion sort + for (i = low + 1; i <= high; i++) { + for (k = i; k > low; k--) { + lo = keys.GetValueImpl (k - 1); + hi = keys.GetValueImpl (k); + if (comparer != null) { + if (comparer.Compare (hi, lo) >= 0) + break; + } else { + if (lo == null) + break; + + if (hi != null) { + cmp = hi as IComparable; + if (cmp.CompareTo (lo) >= 0) + break; + } + } + + swap (keys, items, k - 1, k); + } + } + + continue; + } // calculate the middle element mid = low + ((high - low) / 2); -- 2.25.1