Skip to content
Permalink
master
Switch branches/tags
Go to file
 
 
Cannot retrieve contributors at this time
1056 lines (884 sloc) 33.2 KB
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
/*============================================================
**
**
**
**
**
** Purpose: class to sort arrays
**
**
===========================================================*/
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.CompilerServices;
namespace System.Collections.Generic
{
#region ArraySortHelper for single arrays
internal static class IntrospectiveSortUtilities
{
// This is the threshold where Introspective sort switches to Insertion sort.
// Empirically, 16 seems to speed up most cases without slowing down others, at least for integers.
// Large value types may benefit from a smaller number.
internal const int IntrosortSizeThreshold = 16;
internal static int FloorLog2PlusOne(int n)
{
int result = 0;
while (n >= 1)
{
result++;
n /= 2;
}
return result;
}
[DoesNotReturn]
internal static void ThrowOrIgnoreBadComparer(object? comparer)
{
throw new ArgumentException(SR.Format(SR.Arg_BogusIComparer, comparer));
}
}
internal partial class ArraySortHelper<T>
{
#region IArraySortHelper<T> Members
public void Sort(Span<T> keys, IComparer<T>? comparer)
{
// Add a try block here to detect IComparers (or their
// underlying IComparables, etc) that are bogus.
try
{
comparer ??= Comparer<T>.Default;
IntrospectiveSort(keys, comparer.Compare);
}
catch (IndexOutOfRangeException)
{
IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
}
catch (Exception e)
{
throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
}
}
public int BinarySearch(T[] array, int index, int length, T value, IComparer<T>? comparer)
{
try
{
comparer ??= Comparer<T>.Default;
return InternalBinarySearch(array, index, length, value, comparer);
}
catch (Exception e)
{
throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
}
}
#endregion
internal static void Sort(Span<T> keys, Comparison<T> comparer)
{
Debug.Assert(comparer != null, "Check the arguments in the caller!");
// Add a try block here to detect bogus comparisons
try
{
IntrospectiveSort(keys, comparer);
}
catch (IndexOutOfRangeException)
{
IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
}
catch (Exception e)
{
throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
}
}
internal static int InternalBinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
{
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!");
int lo = index;
int hi = index + length - 1;
while (lo <= hi)
{
int i = lo + ((hi - lo) >> 1);
int order = comparer.Compare(array[i], value);
if (order == 0) return i;
if (order < 0)
{
lo = i + 1;
}
else
{
hi = i - 1;
}
}
return ~lo;
}
private static void SwapIfGreater(Span<T> keys, Comparison<T> comparer, int i, int j)
{
if (i != j)
{
if (comparer(keys[i], keys[j]) > 0)
{
T key = keys[i];
keys[i] = keys[j];
keys[j] = key;
}
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static void Swap(Span<T> a, int i, int j)
{
if (i != j)
{
T t = a[i];
a[i] = a[j];
a[j] = t;
}
}
internal static void IntrospectiveSort(Span<T> keys, Comparison<T> comparer)
{
Debug.Assert(comparer != null);
if (keys.Length > 1)
{
IntroSort(keys, 2 * IntrospectiveSortUtilities.FloorLog2PlusOne(keys.Length), comparer);
}
}
private static void IntroSort(Span<T> keys, int depthLimit, Comparison<T> comparer)
{
int lo = 0;
int hi = keys.Length - 1;
Debug.Assert(comparer != null);
while (hi > lo)
{
int partitionSize = hi - lo + 1;
if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
{
if (partitionSize == 1)
{
return;
}
if (partitionSize == 2)
{
SwapIfGreater(keys, comparer, lo, hi);
return;
}
if (partitionSize == 3)
{
SwapIfGreater(keys, comparer, lo, hi - 1);
SwapIfGreater(keys, comparer, lo, hi);
SwapIfGreater(keys, comparer, hi - 1, hi);
return;
}
InsertionSort(keys[lo..(hi+1)], comparer);
return;
}
if (depthLimit == 0)
{
HeapSort(keys[lo..(hi+1)], comparer);
return;
}
depthLimit--;
int p = PickPivotAndPartition(keys[lo..(hi+1)], comparer);
// Note we've already partitioned around the pivot and do not have to move the pivot again.
IntroSort(keys[(p+1)..(hi+1)], depthLimit, comparer);
hi = p - 1;
}
}
private static int PickPivotAndPartition(Span<T> keys, Comparison<T> comparer)
{
Debug.Assert(comparer != null);
Debug.Assert(!keys.IsEmpty);
int lo = 0;
int hi = keys.Length - 1;
// Compute median-of-three. But also partition them, since we've done the comparison.
int middle = lo + ((hi - lo) / 2);
// Sort lo, mid and hi appropriately, then pick mid as the pivot.
SwapIfGreater(keys, comparer, lo, middle); // swap the low with the mid point
SwapIfGreater(keys, comparer, lo, hi); // swap the low with the high
SwapIfGreater(keys, comparer, middle, hi); // swap the middle with the high
T pivot = keys[middle];
Swap(keys, middle, hi - 1);
int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below.
while (left < right)
{
while (comparer(keys[++left], pivot) < 0) ;
while (comparer(pivot, keys[--right]) < 0) ;
if (left >= right)
break;
Swap(keys, left, right);
}
// Put pivot in the right location.
Swap(keys, left, hi - 1);
return left;
}
private static void HeapSort(Span<T> keys, Comparison<T> comparer)
{
Debug.Assert(comparer != null);
Debug.Assert(!keys.IsEmpty);
int lo = 0;
int hi = keys.Length - 1;
int n = hi - lo + 1;
for (int i = n / 2; i >= 1; i--)
{
DownHeap(keys, i, n, lo, comparer);
}
for (int i = n; i > 1; i--)
{
Swap(keys, lo, lo + i - 1);
DownHeap(keys, 1, i - 1, lo, comparer);
}
}
private static void DownHeap(Span<T> keys, int i, int n, int lo, Comparison<T> comparer)
{
Debug.Assert(comparer != null);
Debug.Assert(lo >= 0);
Debug.Assert(lo < keys.Length);
T d = keys[lo + i - 1];
while (i <= n / 2)
{
int child = 2 * i;
if (child < n && comparer(keys[lo + child - 1], keys[lo + child]) < 0)
{
child++;
}
if (!(comparer(d, keys[lo + child - 1]) < 0))
break;
keys[lo + i - 1] = keys[lo + child - 1];
i = child;
}
keys[lo + i - 1] = d;
}
private static void InsertionSort(Span<T> keys, Comparison<T> comparer)
{
for (int i = 0; i < keys.Length - 1; i++)
{
T t = keys[i + 1];
int j = i;
while (j >= 0 && comparer(t, keys[j]) < 0)
{
keys[j + 1] = keys[j];
j--;
}
keys[j + 1] = t;
}
}
}
internal partial class GenericArraySortHelper<T>
where T : IComparable<T>
{
// Do not add a constructor to this class because ArraySortHelper<T>.CreateSortHelper will not execute it
#region IArraySortHelper<T> Members
public void Sort(Span<T> keys, IComparer<T>? comparer)
{
try
{
if (comparer == null || comparer == Comparer<T>.Default)
{
IntrospectiveSort(keys);
}
else
{
ArraySortHelper<T>.IntrospectiveSort(keys, comparer.Compare);
}
}
catch (IndexOutOfRangeException)
{
IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
}
catch (Exception e)
{
throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
}
}
public int BinarySearch(T[] array, int index, int length, T value, IComparer<T>? comparer)
{
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
{
if (comparer == null || comparer == Comparer<T>.Default)
{
return BinarySearch(array, index, length, value);
}
else
{
return ArraySortHelper<T>.InternalBinarySearch(array, index, length, value, comparer);
}
}
catch (Exception e)
{
throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
}
}
#endregion
// This function is called when the user doesn't specify any comparer.
// Since T is constrained here, we can call IComparable<T>.CompareTo here.
// We can avoid boxing for value type and casting for reference types.
private static int BinarySearch(T[] array, int index, int length, T value)
{
int lo = index;
int hi = index + length - 1;
while (lo <= hi)
{
int i = lo + ((hi - lo) >> 1);
int order;
if (array[i] == null)
{
order = (value == null) ? 0 : -1;
}
else
{
order = array[i].CompareTo(value);
}
if (order == 0)
{
return i;
}
if (order < 0)
{
lo = i + 1;
}
else
{
hi = i - 1;
}
}
return ~lo;
}
private static void SwapIfGreater(Span<T> keys, int i, int j)
{
Debug.Assert(0 <= i && i < keys.Length);
Debug.Assert(0 <= j && j < keys.Length);
if (i != j)
{
if (keys[i] != null && keys[i].CompareTo(keys[j]) > 0)
{
T key = keys[i];
keys[i] = keys[j];
keys[j] = key;
}
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static void Swap(Span<T> a, int i, int j)
{
if (i != j)
{
T t = a[i];
a[i] = a[j];
a[j] = t;
}
}
internal static void IntrospectiveSort(Span<T> keys)
{
if (keys.Length > 1)
{
IntroSort(keys, 2 * IntrospectiveSortUtilities.FloorLog2PlusOne(keys.Length));
}
}
private static void IntroSort(Span<T> keys, int depthLimit)
{
int lo = 0;
int hi = keys.Length - 1;
while (hi > lo)
{
int partitionSize = hi - lo + 1;
if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
{
if (partitionSize == 1)
{
return;
}
if (partitionSize == 2)
{
SwapIfGreater(keys, lo, hi);
return;
}
if (partitionSize == 3)
{
SwapIfGreater(keys, lo, hi - 1);
SwapIfGreater(keys, lo, hi);
SwapIfGreater(keys, hi - 1, hi);
return;
}
InsertionSort(keys[lo..(hi+1)]);
return;
}
if (depthLimit == 0)
{
HeapSort(keys[lo..(hi+1)]);
return;
}
depthLimit--;
int p = PickPivotAndPartition(keys[lo..(hi+1)]);
// Note we've already partitioned around the pivot and do not have to move the pivot again.
IntroSort(keys[(p+1)..(hi+1)], depthLimit);
hi = p - 1;
}
}
private static int PickPivotAndPartition(Span<T> keys)
{
Debug.Assert(!keys.IsEmpty);
int lo = 0;
int hi = keys.Length - 1;
// Compute median-of-three. But also partition them, since we've done the comparison.
int middle = lo + ((hi - lo) / 2);
// Sort lo, mid and hi appropriately, then pick mid as the pivot.
SwapIfGreater(keys, lo, middle); // swap the low with the mid point
SwapIfGreater(keys, lo, hi); // swap the low with the high
SwapIfGreater(keys, middle, hi); // swap the middle with the high
T pivot = keys[middle];
Swap(keys, middle, hi - 1);
int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below.
while (left < right)
{
if (pivot == null)
{
while (left < (hi - 1) && keys[++left] == null) ;
while (right > lo && keys[--right] != null) ;
}
else
{
while (pivot.CompareTo(keys[++left]) > 0) ;
while (pivot.CompareTo(keys[--right]) < 0) ;
}
if (left >= right)
break;
Swap(keys, left, right);
}
// Put pivot in the right location.
Swap(keys, left, hi - 1);
return left;
}
private static void HeapSort(Span<T> keys)
{
Debug.Assert(!keys.IsEmpty);
int lo = 0;
int hi = keys.Length - 1;
int n = hi - lo + 1;
for (int i = n / 2; i >= 1; i = i - 1)
{
DownHeap(keys, i, n, lo);
}
for (int i = n; i > 1; i--)
{
Swap(keys, lo, lo + i - 1);
DownHeap(keys, 1, i - 1, lo);
}
}
private static void DownHeap(Span<T> keys, int i, int n, int lo)
{
Debug.Assert(lo >= 0);
Debug.Assert(lo < keys.Length);
T d = keys[lo + i - 1];
while (i <= n / 2)
{
int child = 2 * i;
if (child < n && (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(keys[lo + child]) < 0))
{
child++;
}
if (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(d) < 0)
break;
keys[lo + i - 1] = keys[lo + child - 1];
i = child;
}
keys[lo + i - 1] = d;
}
private static void InsertionSort(Span<T> keys)
{
for (int i = 0; i < keys.Length - 1; i++)
{
T t = keys[i + 1];
int j = i;
while (j >= 0 && (t == null || t.CompareTo(keys[j]) < 0))
{
keys[j + 1] = keys[j];
j--;
}
keys[j + 1] = t;
}
}
}
#endregion
#region ArraySortHelper for paired key and value arrays
internal partial class ArraySortHelper<TKey, TValue>
{
public void Sort(Span<TKey> keys, Span<TValue> values, IComparer<TKey>? comparer)
{
// Add a try block here to detect IComparers (or their
// underlying IComparables, etc) that are bogus.
try
{
IntrospectiveSort(keys, values, comparer ?? Comparer<TKey>.Default);
}
catch (IndexOutOfRangeException)
{
IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
}
catch (Exception e)
{
throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
}
}
private static void SwapIfGreaterWithValues(Span<TKey> keys, Span<TValue> values, IComparer<TKey> comparer, int i, int j)
{
Debug.Assert(comparer != null);
Debug.Assert(0 <= i && i < keys.Length && i < values.Length);
Debug.Assert(0 <= j && j < keys.Length && j < values.Length);
if (i != j)
{
if (comparer.Compare(keys[i], keys[j]) > 0)
{
TKey key = keys[i];
keys[i] = keys[j];
keys[j] = key;
TValue value = values[i];
values[i] = values[j];
values[j] = value;
}
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static void Swap(Span<TKey> keys, Span<TValue> values, int i, int j)
{
if (i != j)
{
TKey k = keys[i];
keys[i] = keys[j];
keys[j] = k;
TValue v = values[i];
values[i] = values[j];
values[j] = v;
}
}
internal static void IntrospectiveSort(Span<TKey> keys, Span<TValue> values, IComparer<TKey> comparer)
{
Debug.Assert(comparer != null);
Debug.Assert(keys.Length == values.Length);
if (keys.Length > 1)
{
IntroSort(keys, values, 2 * IntrospectiveSortUtilities.FloorLog2PlusOne(keys.Length), comparer);
}
}
private static void IntroSort(Span<TKey> keys, Span<TValue> values, int depthLimit, IComparer<TKey> comparer)
{
Debug.Assert(comparer != null);
int lo = 0;
int hi = keys.Length - 1;
while (hi > lo)
{
int partitionSize = hi - lo + 1;
if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
{
if (partitionSize == 1)
{
return;
}
if (partitionSize == 2)
{
SwapIfGreaterWithValues(keys, values, comparer, lo, hi);
return;
}
if (partitionSize == 3)
{
SwapIfGreaterWithValues(keys, values, comparer, lo, hi - 1);
SwapIfGreaterWithValues(keys, values, comparer, lo, hi);
SwapIfGreaterWithValues(keys, values, comparer, hi - 1, hi);
return;
}
InsertionSort(keys[lo..(hi+1)], values[lo..(hi+1)], comparer);
return;
}
if (depthLimit == 0)
{
HeapSort(keys[lo..(hi+1)], values[lo..(hi+1)], comparer);
return;
}
depthLimit--;
int p = PickPivotAndPartition(keys[lo..(hi+1)], values[lo..(hi+1)], comparer);
// Note we've already partitioned around the pivot and do not have to move the pivot again.
IntroSort(keys[(p+1)..(hi+1)], values[(p+1)..(hi+1)], depthLimit, comparer);
hi = p - 1;
}
}
private static int PickPivotAndPartition(Span<TKey> keys, Span<TValue> values, IComparer<TKey> comparer)
{
Debug.Assert(comparer != null);
Debug.Assert(!keys.IsEmpty);
int lo = 0;
int hi = keys.Length - 1;
// Compute median-of-three. But also partition them, since we've done the comparison.
int middle = lo + ((hi - lo) / 2);
// Sort lo, mid and hi appropriately, then pick mid as the pivot.
SwapIfGreaterWithValues(keys, values, comparer, lo, middle); // swap the low with the mid point
SwapIfGreaterWithValues(keys, values, comparer, lo, hi); // swap the low with the high
SwapIfGreaterWithValues(keys, values, comparer, middle, hi); // swap the middle with the high
TKey pivot = keys[middle];
Swap(keys, values, middle, hi - 1);
int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below.
while (left < right)
{
while (comparer.Compare(keys[++left], pivot) < 0) ;
while (comparer.Compare(pivot, keys[--right]) < 0) ;
if (left >= right)
break;
Swap(keys, values, left, right);
}
// Put pivot in the right location.
Swap(keys, values, left, hi - 1);
return left;
}
private static void HeapSort(Span<TKey> keys, Span<TValue> values, IComparer<TKey> comparer)
{
Debug.Assert(comparer != null);
Debug.Assert(!keys.IsEmpty);
int lo = 0;
int hi = keys.Length - 1;
int n = hi - lo + 1;
for (int i = n / 2; i >= 1; i--)
{
DownHeap(keys, values, i, n, lo, comparer);
}
for (int i = n; i > 1; i--)
{
Swap(keys, values, lo, lo + i - 1);
DownHeap(keys, values, 1, i - 1, lo, comparer);
}
}
private static void DownHeap(Span<TKey> keys, Span<TValue> values, int i, int n, int lo, IComparer<TKey> comparer)
{
Debug.Assert(comparer != null);
Debug.Assert(lo >= 0);
Debug.Assert(lo < keys.Length);
TKey d = keys[lo + i - 1];
TValue dValue = values[lo + i - 1];
while (i <= n / 2)
{
int child = 2 * i;
if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0)
{
child++;
}
if (!(comparer.Compare(d, keys[lo + child - 1]) < 0))
break;
keys[lo + i - 1] = keys[lo + child - 1];
values[lo + i - 1] = values[lo + child - 1];
i = child;
}
keys[lo + i - 1] = d;
values[lo + i - 1] = dValue;
}
private static void InsertionSort(Span<TKey> keys, Span<TValue> values, IComparer<TKey> comparer)
{
Debug.Assert(comparer != null);
for (int i = 0; i < keys.Length - 1; i++)
{
TKey t = keys[i + 1];
TValue tValue = values[i + 1];
int j = i;
while (j >= 0 && comparer.Compare(t, keys[j]) < 0)
{
keys[j + 1] = keys[j];
values[j + 1] = values[j];
j--;
}
keys[j + 1] = t;
values[j + 1] = tValue;
}
}
}
internal partial class GenericArraySortHelper<TKey, TValue>
where TKey : IComparable<TKey>
{
public void Sort(Span<TKey> keys, Span<TValue> values, IComparer<TKey>? comparer)
{
// Add a try block here to detect IComparers (or their
// underlying IComparables, etc) that are bogus.
try
{
if (comparer == null || comparer == Comparer<TKey>.Default)
{
IntrospectiveSort(keys, values);
}
else
{
ArraySortHelper<TKey, TValue>.IntrospectiveSort(keys, values, comparer);
}
}
catch (IndexOutOfRangeException)
{
IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
}
catch (Exception e)
{
throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
}
}
private static void SwapIfGreaterWithValues(Span<TKey> keys, Span<TValue> values, int i, int j)
{
if (i != j)
{
if (keys[i] != null && keys[i].CompareTo(keys[j]) > 0)
{
TKey key = keys[i];
keys[i] = keys[j];
keys[j] = key;
TValue value = values[i];
values[i] = values[j];
values[j] = value;
}
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static void Swap(Span<TKey> keys, Span<TValue> values, int i, int j)
{
if (i != j)
{
TKey k = keys[i];
keys[i] = keys[j];
keys[j] = k;
TValue v = values[i];
values[i] = values[j];
values[j] = v;
}
}
internal static void IntrospectiveSort(Span<TKey> keys, Span<TValue> values)
{
Debug.Assert(keys.Length == values.Length);
if (keys.Length > 1)
{
IntroSort(keys, values, 2 * IntrospectiveSortUtilities.FloorLog2PlusOne(keys.Length));
}
}
private static void IntroSort(Span<TKey> keys, Span<TValue> values, int depthLimit)
{
int lo = 0;
int hi = keys.Length - 1;
while (hi > lo)
{
int partitionSize = hi - lo + 1;
if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
{
if (partitionSize == 1)
{
return;
}
if (partitionSize == 2)
{
SwapIfGreaterWithValues(keys, values, lo, hi);
return;
}
if (partitionSize == 3)
{
SwapIfGreaterWithValues(keys, values, lo, hi - 1);
SwapIfGreaterWithValues(keys, values, lo, hi);
SwapIfGreaterWithValues(keys, values, hi - 1, hi);
return;
}
InsertionSort(keys[lo..(hi+1)], values[lo..(hi+1)]);
return;
}
if (depthLimit == 0)
{
HeapSort(keys[lo..(hi+1)], values[lo..(hi+1)]);
return;
}
depthLimit--;
int p = PickPivotAndPartition(keys[lo..(hi+1)], values[lo..(hi+1)]);
// Note we've already partitioned around the pivot and do not have to move the pivot again.
IntroSort(keys[(p+1)..(hi+1)], values[(p+1)..(hi+1)], depthLimit);
hi = p - 1;
}
}
private static int PickPivotAndPartition(Span<TKey> keys, Span<TValue> values)
{
Debug.Assert(!keys.IsEmpty);
int lo = 0;
int hi = keys.Length - 1;
// Compute median-of-three. But also partition them, since we've done the comparison.
int middle = lo + ((hi - lo) / 2);
// Sort lo, mid and hi appropriately, then pick mid as the pivot.
SwapIfGreaterWithValues(keys, values, lo, middle); // swap the low with the mid point
SwapIfGreaterWithValues(keys, values, lo, hi); // swap the low with the high
SwapIfGreaterWithValues(keys, values, middle, hi); // swap the middle with the high
TKey pivot = keys[middle];
Swap(keys, values, middle, hi - 1);
int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below.
while (left < right)
{
if (pivot == null)
{
while (left < (hi - 1) && keys[++left] == null) ;
while (right > lo && keys[--right] != null) ;
}
else
{
while (pivot.CompareTo(keys[++left]) > 0) ;
while (pivot.CompareTo(keys[--right]) < 0) ;
}
if (left >= right)
break;
Swap(keys, values, left, right);
}
// Put pivot in the right location.
Swap(keys, values, left, hi - 1);
return left;
}
private static void HeapSort(Span<TKey> keys, Span<TValue> values)
{
Debug.Assert(!keys.IsEmpty);
int lo = 0;
int hi = keys.Length - 1;
int n = hi - lo + 1;
for (int i = n / 2; i >= 1; i--)
{
DownHeap(keys, values, i, n, lo);
}
for (int i = n; i > 1; i--)
{
Swap(keys, values, lo, lo + i - 1);
DownHeap(keys, values, 1, i - 1, lo);
}
}
private static void DownHeap(Span<TKey> keys, Span<TValue> values, int i, int n, int lo)
{
Debug.Assert(lo >= 0);
Debug.Assert(lo < keys.Length);
TKey d = keys[lo + i - 1];
TValue dValue = values[lo + i - 1];
while (i <= n / 2)
{
int child = 2 * i;
if (child < n && (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(keys[lo + child]) < 0))
{
child++;
}
if (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(d) < 0)
break;
keys[lo + i - 1] = keys[lo + child - 1];
values[lo + i - 1] = values[lo + child - 1];
i = child;
}
keys[lo + i - 1] = d;
values[lo + i - 1] = dValue;
}
private static void InsertionSort(Span<TKey> keys, Span<TValue> values)
{
for (int i = 0; i < keys.Length - 1; i++)
{
TKey t = keys[i + 1];
TValue tValue = values[i + 1];
int j = i;
while (j >= 0 && (t == null || t.CompareTo(keys[j]) < 0))
{
keys[j + 1] = keys[j];
values[j + 1] = values[j];
j--;
}
keys[j + 1] = t;
values[j + 1] = tValue;
}
}
}
#endregion
}