summaryrefslogtreecommitdiff
path: root/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs
diff options
context:
space:
mode:
Diffstat (limited to 'src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs')
-rw-r--r--src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs452
1 files changed, 52 insertions, 400 deletions
diff --git a/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs b/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs
index b2fed9d78f..298ac3e177 100644
--- a/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs
+++ b/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs
@@ -17,6 +17,7 @@ namespace System.Collections.Generic
using System;
using System.Globalization;
using System.Runtime.CompilerServices;
+ using System.Diagnostics;
using System.Diagnostics.Contracts;
using System.Runtime.Versioning;
@@ -49,16 +50,7 @@ namespace System.Collections.Generic
}
internal static void ThrowOrIgnoreBadComparer(Object comparer) {
- // This is hit when an invarant of QuickSort is violated due to a bad IComparer implementation (for
- // example, imagine an IComparer that returns 0 when items are equal but -1 all other times).
- //
- // We could have thrown this exception on v4, but due to changes in v4.5 around how we partition arrays
- // there are different sets of input where we would throw this exception. In order to reduce overall risk from
- // an app compat persective, we're changing to never throw on v4. Instead, we'll return with a partially
- // sorted array.
- if(BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) {
- throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", comparer));
- }
+ throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", comparer));
}
}
@@ -81,7 +73,6 @@ namespace System.Collections.Generic
}
}
- [System.Security.SecuritySafeCritical] // auto-generated
private static IArraySortHelper<T> CreateArraySortHelper()
{
if (typeof(IComparable<T>).IsAssignableFrom(typeof(T)))
@@ -99,8 +90,8 @@ namespace System.Collections.Generic
public void Sort(T[] keys, int index, int length, IComparer<T> comparer)
{
- Contract.Assert(keys != null, "Check the arguments in the caller!");
- Contract.Assert( index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
+ Debug.Assert(keys != null, "Check the arguments in the caller!");
+ Debug.Assert( index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
// Add a try block here to detect IComparers (or their
// underlying IComparables, etc) that are bogus.
@@ -111,22 +102,7 @@ namespace System.Collections.Generic
comparer = Comparer<T>.Default;
}
-#if FEATURE_CORECLR
- // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade
- // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka
- // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
-
- IntrospectiveSort(keys, index, length, comparer);
-#else
- if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
- {
- IntrospectiveSort(keys, index, length, comparer);
- }
- else
- {
- DepthLimitedQuickSort(keys, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold);
- }
-#endif
+ IntrospectiveSort(keys, index, length, comparer.Compare);
}
catch (IndexOutOfRangeException)
{
@@ -157,6 +133,27 @@ namespace System.Collections.Generic
#endregion
+ internal static void Sort(T[] keys, int index, int length, Comparison<T> comparer)
+ {
+ Debug.Assert(keys != null, "Check the arguments in the caller!");
+ Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
+ Debug.Assert(comparer != null, "Check the arguments in the caller!");
+
+ // Add a try block here to detect bogus comparisons
+ try
+ {
+ IntrospectiveSort(keys, index, length, comparer);
+ }
+ catch (IndexOutOfRangeException)
+ {
+ IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
+ }
+ catch (Exception e)
+ {
+ throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
+ }
+ }
+
internal static int InternalBinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
{
Contract.Requires(array != null, "Check the arguments in the caller!");
@@ -183,11 +180,11 @@ namespace System.Collections.Generic
return ~lo;
}
- private static void SwapIfGreater(T[] keys, IComparer<T> comparer, int a, int b)
+ private static void SwapIfGreater(T[] keys, Comparison<T> comparer, int a, int b)
{
if (a != b)
{
- if (comparer.Compare(keys[a], keys[b]) > 0)
+ if (comparer(keys[a], keys[b]) > 0)
{
T key = keys[a];
keys[a] = keys[b];
@@ -198,7 +195,7 @@ namespace System.Collections.Generic
private static void Swap(T[] a, int i, int j)
{
- if(i != j)
+ if (i != j)
{
T t = a[i];
a[i] = a[j];
@@ -206,63 +203,7 @@ namespace System.Collections.Generic
}
}
- internal static void DepthLimitedQuickSort(T[] keys, int left, int right, IComparer<T> comparer, int depthLimit)
- {
- do
- {
- if (depthLimit == 0)
- {
- Heapsort(keys, left, right, comparer);
- return;
- }
-
- int i = left;
- int j = right;
-
- // pre-sort the low, middle (pivot), and high values in place.
- // this improves performance in the face of already sorted data, or
- // data that is made up of multiple sorted runs appended together.
- int middle = i + ((j - i) >> 1);
- SwapIfGreater(keys, comparer, i, middle); // swap the low with the mid point
- SwapIfGreater(keys, comparer, i, j); // swap the low with the high
- SwapIfGreater(keys, comparer, middle, j); // swap the middle with the high
-
- T x = keys[middle];
- do
- {
- while (comparer.Compare(keys[i], x) < 0) i++;
- while (comparer.Compare(x, keys[j]) < 0) j--;
- Contract.Assert(i >= left && j <= right, "(i>=left && j<=right) Sort failed - Is your IComparer bogus?");
- if (i > j) break;
- if (i < j)
- {
- T key = keys[i];
- keys[i] = keys[j];
- keys[j] = key;
- }
- i++;
- j--;
- } while (i <= j);
-
- // The next iteration of the while loop is to "recursively" sort the larger half of the array and the
- // following calls recursively sort the smaller half. So we subtract one from depthLimit here so
- // both sorts see the new value.
- depthLimit--;
-
- if (j - left <= right - i)
- {
- if (left < j) DepthLimitedQuickSort(keys, left, j, comparer, depthLimit);
- left = i;
- }
- else
- {
- if (i < right) DepthLimitedQuickSort(keys, i, right, comparer, depthLimit);
- right = j;
- }
- } while (left < right);
- }
-
- internal static void IntrospectiveSort(T[] keys, int left, int length, IComparer<T> comparer)
+ internal static void IntrospectiveSort(T[] keys, int left, int length, Comparison<T> comparer)
{
Contract.Requires(keys != null);
Contract.Requires(comparer != null);
@@ -277,7 +218,7 @@ namespace System.Collections.Generic
IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer);
}
- private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, IComparer<T> comparer)
+ private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, Comparison<T> comparer)
{
Contract.Requires(keys != null);
Contract.Requires(comparer != null);
@@ -324,7 +265,7 @@ namespace System.Collections.Generic
}
}
- private static int PickPivotAndPartition(T[] keys, int lo, int hi, IComparer<T> comparer)
+ private static int PickPivotAndPartition(T[] keys, int lo, int hi, Comparison<T> comparer)
{
Contract.Requires(keys != null);
Contract.Requires(comparer != null);
@@ -347,8 +288,8 @@ namespace System.Collections.Generic
while (left < right)
{
- while (comparer.Compare(keys[++left], pivot) < 0) ;
- while (comparer.Compare(pivot, keys[--right]) < 0) ;
+ while (comparer(keys[++left], pivot) < 0) ;
+ while (comparer(pivot, keys[--right]) < 0) ;
if (left >= right)
break;
@@ -361,7 +302,7 @@ namespace System.Collections.Generic
return left;
}
- private static void Heapsort(T[] keys, int lo, int hi, IComparer<T> comparer)
+ private static void Heapsort(T[] keys, int lo, int hi, Comparison<T> comparer)
{
Contract.Requires(keys != null);
Contract.Requires(comparer != null);
@@ -381,7 +322,7 @@ namespace System.Collections.Generic
}
}
- private static void DownHeap(T[] keys, int i, int n, int lo, IComparer<T> comparer)
+ private static void DownHeap(T[] keys, int i, int n, int lo, Comparison<T> comparer)
{
Contract.Requires(keys != null);
Contract.Requires(comparer != null);
@@ -393,11 +334,11 @@ namespace System.Collections.Generic
while (i <= n / 2)
{
child = 2 * i;
- if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0)
+ if (child < n && comparer(keys[lo + child - 1], keys[lo + child]) < 0)
{
child++;
}
- if (!(comparer.Compare(d, keys[lo + child - 1]) < 0))
+ if (!(comparer(d, keys[lo + child - 1]) < 0))
break;
keys[lo + i - 1] = keys[lo + child - 1];
i = child;
@@ -405,7 +346,7 @@ namespace System.Collections.Generic
keys[lo + i - 1] = d;
}
- private static void InsertionSort(T[] keys, int lo, int hi, IComparer<T> comparer)
+ private static void InsertionSort(T[] keys, int lo, int hi, Comparison<T> comparer)
{
Contract.Requires(keys != null);
Contract.Requires(lo >= 0);
@@ -418,7 +359,7 @@ namespace System.Collections.Generic
{
j = i;
t = keys[i + 1];
- while (j >= lo && comparer.Compare(t, keys[j]) < 0)
+ while (j >= lo && comparer(t, keys[j]) < 0)
{
keys[j + 1] = keys[j];
j--;
@@ -439,49 +380,18 @@ namespace System.Collections.Generic
public void Sort(T[] keys, int index, int length, IComparer<T> comparer)
{
- Contract.Assert(keys != null, "Check the arguments in the caller!");
- Contract.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
+ Debug.Assert(keys != null, "Check the arguments in the caller!");
+ Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
try
{
- if (comparer == null || comparer == Comparer<T>.Default) {
-
-#if FEATURE_CORECLR
- // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade
- // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka
- // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
-
+ if (comparer == null || comparer == Comparer<T>.Default)
+ {
IntrospectiveSort(keys, index, length);
-#else
- // call the faster version of our sort algorithm if the user doesn't provide a comparer
- if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
- {
- IntrospectiveSort(keys, index, length);
- }
- else
- {
- DepthLimitedQuickSort(keys, index, length + index - 1, IntrospectiveSortUtilities.QuickSortDepthThreshold);
- }
-#endif
}
else
{
-#if FEATURE_CORECLR
- // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade
- // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka
- // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
-
- ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer);
-#else
- if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
- {
- ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer);
- }
- else
- {
- ArraySortHelper<T>.DepthLimitedQuickSort(keys, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold);
- }
-#endif
+ ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer.Compare);
}
}
catch (IndexOutOfRangeException)
@@ -496,8 +406,8 @@ namespace System.Collections.Generic
public int BinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
{
- Contract.Assert(array != null, "Check the arguments in the caller!");
- Contract.Assert(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!");
+ Debug.Assert(array != null, "Check the arguments in the caller!");
+ Debug.Assert(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!");
try
{
@@ -583,78 +493,6 @@ namespace System.Collections.Generic
}
}
- private static void DepthLimitedQuickSort(T[] keys, int left, int right, int depthLimit)
- {
- Contract.Requires(keys != null);
- Contract.Requires(0 <= left && left < keys.Length);
- Contract.Requires(0 <= right && right < keys.Length);
-
- // The code in this function looks very similar to QuickSort in ArraySortHelper<T> class.
- // The difference is that T is constrainted to IComparable<T> here.
- // So the IL code will be different. This function is faster than the one in ArraySortHelper<T>.
-
- do
- {
- if (depthLimit == 0)
- {
- Heapsort(keys, left, right);
- return;
- }
-
- int i = left;
- int j = right;
-
- // pre-sort the low, middle (pivot), and high values in place.
- // this improves performance in the face of already sorted data, or
- // data that is made up of multiple sorted runs appended together.
- int middle = i + ((j - i) >> 1);
- SwapIfGreaterWithItems(keys, i, middle); // swap the low with the mid point
- SwapIfGreaterWithItems(keys, i, j); // swap the low with the high
- SwapIfGreaterWithItems(keys, middle, j); // swap the middle with the high
-
- T x = keys[middle];
- do
- {
- if (x == null)
- {
- // if x null, the loop to find two elements to be switched can be reduced.
- while (keys[j] != null) j--;
- }
- else
- {
- while (x.CompareTo(keys[i]) > 0) i++;
- while (x.CompareTo(keys[j]) < 0) j--;
- }
- Contract.Assert(i >= left && j <= right, "(i>=left && j<=right) Sort failed - Is your IComparer bogus?");
- if (i > j) break;
- if (i < j)
- {
- T key = keys[i];
- keys[i] = keys[j];
- keys[j] = key;
- }
- i++;
- j--;
- } while (i <= j);
-
- // The next iteration of the while loop is to "recursively" sort the larger half of the array and the
- // following calls recursively sort the smaller half. So we subtract one from depthLimit here so
- // both sorts see the new value.
- depthLimit--;
-
- if (j - left <= right - i)
- {
- if (left < j) DepthLimitedQuickSort(keys, left, j, depthLimit);
- left = i;
- }
- else
- {
- if (i < right) DepthLimitedQuickSort(keys, i, right, depthLimit);
- right = j;
- }
- } while (left < right);
- }
-
internal static void IntrospectiveSort(T[] keys, int left, int length)
{
Contract.Requires(keys != null);
@@ -824,7 +662,7 @@ namespace System.Collections.Generic
}
}
- #endregion
+#endregion
#region ArraySortHelper for paired key and value arrays
@@ -851,7 +689,6 @@ namespace System.Collections.Generic
}
}
- [System.Security.SecuritySafeCritical] // auto-generated
private static IArraySortHelper<TKey, TValue> CreateArraySortHelper()
{
if (typeof(IComparable<TKey>).IsAssignableFrom(typeof(TKey)))
@@ -867,8 +704,8 @@ namespace System.Collections.Generic
public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer)
{
- Contract.Assert(keys != null, "Check the arguments in the caller!"); // Precondition on interface method
- Contract.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
+ Debug.Assert(keys != null, "Check the arguments in the caller!"); // Precondition on interface method
+ Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
// Add a try block here to detect IComparers (or their
// underlying IComparables, etc) that are bogus.
@@ -879,22 +716,7 @@ namespace System.Collections.Generic
comparer = Comparer<TKey>.Default;
}
-#if FEATURE_CORECLR
- // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade
- // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka
- // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
-
IntrospectiveSort(keys, values, index, length, comparer);
-#else
- if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
- {
- IntrospectiveSort(keys, values, index, length, comparer);
- }
- else
- {
- DepthLimitedQuickSort(keys, values, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold);
- }
-#endif
}
catch (IndexOutOfRangeException)
{
@@ -947,68 +769,6 @@ namespace System.Collections.Generic
}
}
- internal static void DepthLimitedQuickSort(TKey[] keys, TValue[] values, int left, int right, IComparer<TKey> comparer, int depthLimit)
- {
- do
- {
- if (depthLimit == 0)
- {
- Heapsort(keys, values, left, right, comparer);
- return;
- }
-
- int i = left;
- int j = right;
-
- // pre-sort the low, middle (pivot), and high values in place.
- // this improves performance in the face of already sorted data, or
- // data that is made up of multiple sorted runs appended together.
- int middle = i + ((j - i) >> 1);
- SwapIfGreaterWithItems(keys, values, comparer, i, middle); // swap the low with the mid point
- SwapIfGreaterWithItems(keys, values, comparer, i, j); // swap the low with the high
- SwapIfGreaterWithItems(keys, values, comparer, middle, j); // swap the middle with the high
-
- TKey x = keys[middle];
- do
- {
- while (comparer.Compare(keys[i], x) < 0) i++;
- while (comparer.Compare(x, keys[j]) < 0) j--;
- Contract.Assert(i >= left && j <= right, "(i>=left && j<=right) Sort failed - Is your IComparer bogus?");
- if (i > j) break;
- if (i < j)
- {
- TKey key = keys[i];
- keys[i] = keys[j];
- keys[j] = key;
- if (values != null)
- {
- TValue value = values[i];
- values[i] = values[j];
- values[j] = value;
- }
- }
- i++;
- j--;
- } while (i <= j);
-
- // The next iteration of the while loop is to "recursively" sort the larger half of the array and the
- // following calls recursively sort the smaller half. So we subtract one from depthLimit here so
- // both sorts see the new value.
- depthLimit--;
-
- if (j - left <= right - i)
- {
- if (left < j) DepthLimitedQuickSort(keys, values, left, j, comparer, depthLimit);
- left = i;
- }
- else
- {
- if (i < right) DepthLimitedQuickSort(keys, values, i, right, comparer, depthLimit);
- right = j;
- }
- } while (left < right);
- }
-
internal static void IntrospectiveSort(TKey[] keys, TValue[] values, int left, int length, IComparer<TKey> comparer)
{
Contract.Requires(keys != null);
@@ -1199,8 +959,8 @@ namespace System.Collections.Generic
{
public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer)
{
- Contract.Assert(keys != null, "Check the arguments in the caller!");
- Contract.Assert( index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
+ Debug.Assert(keys != null, "Check the arguments in the caller!");
+ Debug.Assert( index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
// Add a try block here to detect IComparers (or their
// underlying IComparables, etc) that are bogus.
@@ -1208,44 +968,12 @@ namespace System.Collections.Generic
{
if (comparer == null || comparer == Comparer<TKey>.Default)
{
-#if FEATURE_CORECLR
- // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade
- // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka
- // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
-
IntrospectiveSort(keys, values, index, length);
-#else
- // call the faster version of our sort algorithm if the user doesn't provide a comparer
- if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
- {
- IntrospectiveSort(keys, values, index, length);
- }
- else
- {
- DepthLimitedQuickSort(keys, values, index, length + index - 1, IntrospectiveSortUtilities.QuickSortDepthThreshold);
- }
-#endif
}
else
{
-#if FEATURE_CORECLR
- // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade
- // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka
- // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
-
ArraySortHelper<TKey, TValue>.IntrospectiveSort(keys, values, index, length, comparer);
-#else
- if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
- {
- ArraySortHelper<TKey, TValue>.IntrospectiveSort(keys, values, index, length, comparer);
- }
- else
- {
- ArraySortHelper<TKey, TValue>.DepthLimitedQuickSort(keys, values, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold);
- }
-#endif
}
-
}
catch (IndexOutOfRangeException)
{
@@ -1292,80 +1020,6 @@ namespace System.Collections.Generic
}
}
- private static void DepthLimitedQuickSort(TKey[] keys, TValue[] values, int left, int right, int depthLimit)
- {
- // The code in this function looks very similar to QuickSort in ArraySortHelper<T> class.
- // The difference is that T is constrainted to IComparable<T> here.
- // So the IL code will be different. This function is faster than the one in ArraySortHelper<T>.
-
- do
- {
- if (depthLimit == 0)
- {
- Heapsort(keys, values, left, right);
- return;
- }
-
- int i = left;
- int j = right;
-
- // pre-sort the low, middle (pivot), and high values in place.
- // this improves performance in the face of already sorted data, or
- // data that is made up of multiple sorted runs appended together.
- int middle = i + ((j - i) >> 1);
- SwapIfGreaterWithItems(keys, values, i, middle); // swap the low with the mid point
- SwapIfGreaterWithItems(keys, values, i, j); // swap the low with the high
- SwapIfGreaterWithItems(keys, values, middle, j); // swap the middle with the high
-
- TKey x = keys[middle];
- do
- {
- if (x == null)
- {
- // if x null, the loop to find two elements to be switched can be reduced.
- while (keys[j] != null) j--;
- }
- else
- {
- while (x.CompareTo(keys[i]) > 0) i++;
- while (x.CompareTo(keys[j]) < 0) j--;
- }
- Contract.Assert(i >= left && j <= right, "(i>=left && j<=right) Sort failed - Is your IComparer bogus?");
- if (i > j) break;
- if (i < j)
- {
- TKey key = keys[i];
- keys[i] = keys[j];
- keys[j] = key;
- if (values != null)
- {
- TValue value = values[i];
- values[i] = values[j];
- values[j] = value;
- }
- }
- i++;
- j--;
- } while (i <= j);
-
- // The next iteration of the while loop is to "recursively" sort the larger half of the array and the
- // following calls recursively sort the smaller half. So we subtract one from depthLimit here so
- // both sorts see the new value.
- depthLimit--;
-
- if (j - left <= right - i)
- {
- if (left < j) DepthLimitedQuickSort(keys, values, left, j, depthLimit);
- left = i;
- }
- else
- {
- if (i < right) DepthLimitedQuickSort(keys, values, i, right, depthLimit);
- right = j;
- }
- } while (left < right);
- }
-
internal static void IntrospectiveSort(TKey[] keys, TValue[] values, int left, int length)
{
Contract.Requires(keys != null);
@@ -1554,5 +1208,3 @@ namespace System.Collections.Generic
#endregion
}
-
-