mcs/class/corlib/coreclr/ArraySortHelper.cs

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5 /*============================================================
   6 **
   7 **
   8 **
   9 **
  10 **
  11 ** Purpose: class to sort arrays
  12 **
  13 **
  14 ===========================================================*/
  15
  16 using System;
  17 using System.Globalization;
  18 using System.Runtime.CompilerServices;
  19 using System.Diagnostics;
  20 using System.Diagnostics.Contracts;
  21 using System.Runtime.Versioning;
  22 #if MONO
  23 using System.Diagnostics.Private;
  24 #endif
  25
  26 namespace System.Collections.Generic
  27 {
  28     #region ArraySortHelper for single arrays
  29
  30     internal interface IArraySortHelper<TKey>
  31     {
  32         void Sort(TKey[] keys, int index, int length, IComparer<TKey> comparer);
  33         int BinarySearch(TKey[] keys, int index, int length, TKey value, IComparer<TKey> comparer);
  34     }
  35
  36     internal static class IntrospectiveSortUtilities
  37     {
  38         // This is the threshold where Introspective sort switches to Insertion sort.
  39         // Imperically, 16 seems to speed up most cases without slowing down others, at least for integers.
  40         // Large value types may benefit from a smaller number.
  41         internal const int IntrosortSizeThreshold = 16;
  42
  43         internal static int FloorLog2(int n)
  44         {
  45             int result = 0;
  46             while (n >= 1)
  47             {
  48                 result++;
  49                 n = n / 2;
  50             }
  51             return result;
  52         }
  53
  54         internal static void ThrowOrIgnoreBadComparer(Object comparer)
  55         {
  56             throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", comparer));
  57         }
  58     }
  59
  60     [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`1")]
  61     internal class ArraySortHelper<T>
  62         : IArraySortHelper<T>
  63     {
  64         private static volatile IArraySortHelper<T> defaultArraySortHelper;
  65
  66         public static IArraySortHelper<T> Default
  67         {
  68             get
  69             {
  70                 IArraySortHelper<T> sorter = defaultArraySortHelper;
  71                 if (sorter == null)
  72                     sorter = CreateArraySortHelper();
  73
  74                 return sorter;
  75             }
  76         }
  77
  78         private static IArraySortHelper<T> CreateArraySortHelper()
  79         {
  80 #if !MONO
  81             if (typeof(IComparable<T>).IsAssignableFrom(typeof(T)))
  82             {
  83                 defaultArraySortHelper = (IArraySortHelper<T>)RuntimeTypeHandle.Allocate(typeof(GenericArraySortHelper<string>).TypeHandle.Instantiate(new Type[] { typeof(T) }));
  84             }
  85             else
  86 #endif
  87             {
  88                 defaultArraySortHelper = new ArraySortHelper<T>();
  89             }
  90             return defaultArraySortHelper;
  91         }
  92
  93         #region IArraySortHelper<T> Members
  94
  95         public void Sort(T[] keys, int index, int length, IComparer<T> comparer)
  96         {
  97             Debug.Assert(keys != null, "Check the arguments in the caller!");
  98             Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
  99
 100             // Add a try block here to detect IComparers (or their
 101             // underlying IComparables, etc) that are bogus.
 102             try
 103             {
 104                 if (comparer == null)
 105                 {
 106                     comparer = Comparer<T>.Default;
 107                 }
 108
 109                 IntrospectiveSort(keys, index, length, comparer.Compare);
 110             }
 111             catch (IndexOutOfRangeException)
 112             {
 113                 IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
 114             }
 115             catch (Exception e)
 116             {
 117                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
 118             }
 119         }
 120
 121         public int BinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
 122         {
 123             try
 124             {
 125                 if (comparer == null)
 126                 {
 127                     comparer = Comparer<T>.Default;
 128                 }
 129
 130                 return InternalBinarySearch(array, index, length, value, comparer);
 131             }
 132             catch (Exception e)
 133             {
 134                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
 135             }
 136         }
 137
 138         #endregion
 139
 140         internal static void Sort(T[] keys, int index, int length, Comparison<T> comparer)
 141         {
 142             Debug.Assert(keys != null, "Check the arguments in the caller!");
 143             Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
 144             Debug.Assert(comparer != null, "Check the arguments in the caller!");
 145
 146             // Add a try block here to detect bogus comparisons
 147             try
 148             {
 149                 IntrospectiveSort(keys, index, length, comparer);
 150             }
 151             catch (IndexOutOfRangeException)
 152             {
 153                 IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
 154             }
 155             catch (Exception e)
 156             {
 157                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
 158             }
 159         }
 160
 161         internal static int InternalBinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
 162         {
 163             Contract.Requires(array != null, "Check the arguments in the caller!");
 164             Contract.Requires(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!");
 165
 166             int lo = index;
 167             int hi = index + length - 1;
 168             while (lo <= hi)
 169             {
 170                 int i = lo + ((hi - lo) >> 1);
 171                 int order = comparer.Compare(array[i], value);
 172
 173                 if (order == 0) return i;
 174                 if (order < 0)
 175                 {
 176                     lo = i + 1;
 177                 }
 178                 else
 179                 {
 180                     hi = i - 1;
 181                 }
 182             }
 183
 184             return ~lo;
 185         }
 186
 187         private static void SwapIfGreater(T[] keys, Comparison<T> comparer, int a, int b)
 188         {
 189             if (a != b)
 190             {
 191                 if (comparer(keys[a], keys[b]) > 0)
 192                 {
 193                     T key = keys[a];
 194                     keys[a] = keys[b];
 195                     keys[b] = key;
 196                 }
 197             }
 198         }
 199
 200         private static void Swap(T[] a, int i, int j)
 201         {
 202             if (i != j)
 203             {
 204                 T t = a[i];
 205                 a[i] = a[j];
 206                 a[j] = t;
 207             }
 208         }
 209
 210         internal static void IntrospectiveSort(T[] keys, int left, int length, Comparison<T> comparer)
 211         {
 212             Contract.Requires(keys != null);
 213             Contract.Requires(comparer != null);
 214             Contract.Requires(left >= 0);
 215             Contract.Requires(length >= 0);
 216             Contract.Requires(length <= keys.Length);
 217             Contract.Requires(length + left <= keys.Length);
 218
 219             if (length < 2)
 220                 return;
 221
 222             IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer);
 223         }
 224
 225         private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, Comparison<T> comparer)
 226         {
 227             Contract.Requires(keys != null);
 228             Contract.Requires(comparer != null);
 229             Contract.Requires(lo >= 0);
 230             Contract.Requires(hi < keys.Length);
 231
 232             while (hi > lo)
 233             {
 234                 int partitionSize = hi - lo + 1;
 235                 if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
 236                 {
 237                     if (partitionSize == 1)
 238                     {
 239                         return;
 240                     }
 241                     if (partitionSize == 2)
 242                     {
 243                         SwapIfGreater(keys, comparer, lo, hi);
 244                         return;
 245                     }
 246                     if (partitionSize == 3)
 247                     {
 248                         SwapIfGreater(keys, comparer, lo, hi - 1);
 249                         SwapIfGreater(keys, comparer, lo, hi);
 250                         SwapIfGreater(keys, comparer, hi - 1, hi);
 251                         return;
 252                     }
 253
 254                     InsertionSort(keys, lo, hi, comparer);
 255                     return;
 256                 }
 257
 258                 if (depthLimit == 0)
 259                 {
 260                     Heapsort(keys, lo, hi, comparer);
 261                     return;
 262                 }
 263                 depthLimit--;
 264
 265                 int p = PickPivotAndPartition(keys, lo, hi, comparer);
 266                 // Note we've already partitioned around the pivot and do not have to move the pivot again.
 267                 IntroSort(keys, p + 1, hi, depthLimit, comparer);
 268                 hi = p - 1;
 269             }
 270         }
 271
 272         private static int PickPivotAndPartition(T[] keys, int lo, int hi, Comparison<T> comparer)
 273         {
 274             Contract.Requires(keys != null);
 275             Contract.Requires(comparer != null);
 276             Contract.Requires(lo >= 0);
 277             Contract.Requires(hi > lo);
 278             Contract.Requires(hi < keys.Length);
 279             Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi);
 280
 281             // Compute median-of-three.  But also partition them, since we've done the comparison.
 282             int middle = lo + ((hi - lo) / 2);
 283
 284             // Sort lo, mid and hi appropriately, then pick mid as the pivot.
 285             SwapIfGreater(keys, comparer, lo, middle);  // swap the low with the mid point
 286             SwapIfGreater(keys, comparer, lo, hi);   // swap the low with the high
 287             SwapIfGreater(keys, comparer, middle, hi); // swap the middle with the high
 288
 289             T pivot = keys[middle];
 290             Swap(keys, middle, hi - 1);
 291             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.
 292
 293             while (left < right)
 294             {
 295                 while (comparer(keys[++left], pivot) < 0) ;
 296                 while (comparer(pivot, keys[--right]) < 0) ;
 297
 298                 if (left >= right)
 299                     break;
 300
 301                 Swap(keys, left, right);
 302             }
 303
 304             // Put pivot in the right location.
 305             Swap(keys, left, (hi - 1));
 306             return left;
 307         }
 308
 309         private static void Heapsort(T[] keys, int lo, int hi, Comparison<T> comparer)
 310         {
 311             Contract.Requires(keys != null);
 312             Contract.Requires(comparer != null);
 313             Contract.Requires(lo >= 0);
 314             Contract.Requires(hi > lo);
 315             Contract.Requires(hi < keys.Length);
 316
 317             int n = hi - lo + 1;
 318             for (int i = n / 2; i >= 1; i = i - 1)
 319             {
 320                 DownHeap(keys, i, n, lo, comparer);
 321             }
 322             for (int i = n; i > 1; i = i - 1)
 323             {
 324                 Swap(keys, lo, lo + i - 1);
 325                 DownHeap(keys, 1, i - 1, lo, comparer);
 326             }
 327         }
 328
 329         private static void DownHeap(T[] keys, int i, int n, int lo, Comparison<T> comparer)
 330         {
 331             Contract.Requires(keys != null);
 332             Contract.Requires(comparer != null);
 333             Contract.Requires(lo >= 0);
 334             Contract.Requires(lo < keys.Length);
 335
 336             T d = keys[lo + i - 1];
 337             int child;
 338             while (i <= n / 2)
 339             {
 340                 child = 2 * i;
 341                 if (child < n && comparer(keys[lo + child - 1], keys[lo + child]) < 0)
 342                 {
 343                     child++;
 344                 }
 345                 if (!(comparer(d, keys[lo + child - 1]) < 0))
 346                     break;
 347                 keys[lo + i - 1] = keys[lo + child - 1];
 348                 i = child;
 349             }
 350             keys[lo + i - 1] = d;
 351         }
 352
 353         private static void InsertionSort(T[] keys, int lo, int hi, Comparison<T> comparer)
 354         {
 355             Contract.Requires(keys != null);
 356             Contract.Requires(lo >= 0);
 357             Contract.Requires(hi >= lo);
 358             Contract.Requires(hi <= keys.Length);
 359
 360             int i, j;
 361             T t;
 362             for (i = lo; i < hi; i++)
 363             {
 364                 j = i;
 365                 t = keys[i + 1];
 366                 while (j >= lo && comparer(t, keys[j]) < 0)
 367                 {
 368                     keys[j + 1] = keys[j];
 369                     j--;
 370                 }
 371                 keys[j + 1] = t;
 372             }
 373         }
 374     }
 375
 376     [Serializable()]
 377     internal class GenericArraySortHelper<T>
 378         : IArraySortHelper<T>
 379         where T : IComparable<T>
 380     {
 381         // Do not add a constructor to this class because ArraySortHelper<T>.CreateSortHelper will not execute it
 382
 383         #region IArraySortHelper<T> Members
 384
 385         public void Sort(T[] keys, int index, int length, IComparer<T> comparer)
 386         {
 387             Debug.Assert(keys != null, "Check the arguments in the caller!");
 388             Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
 389
 390             try
 391             {
 392                 if (comparer == null || comparer == Comparer<T>.Default)
 393                 {
 394                     IntrospectiveSort(keys, index, length);
 395                 }
 396                 else
 397                 {
 398                     ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer.Compare);
 399                 }
 400             }
 401             catch (IndexOutOfRangeException)
 402             {
 403                 IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
 404             }
 405             catch (Exception e)
 406             {
 407                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
 408             }
 409         }
 410
 411         public int BinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
 412         {
 413             Debug.Assert(array != null, "Check the arguments in the caller!");
 414             Debug.Assert(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!");
 415
 416             try
 417             {
 418                 if (comparer == null || comparer == Comparer<T>.Default)
 419                 {
 420                     return BinarySearch(array, index, length, value);
 421                 }
 422                 else
 423                 {
 424                     return ArraySortHelper<T>.InternalBinarySearch(array, index, length, value, comparer);
 425                 }
 426             }
 427             catch (Exception e)
 428             {
 429                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
 430             }
 431         }
 432
 433         #endregion
 434
 435         // This function is called when the user doesn't specify any comparer.
 436         // Since T is constrained here, we can call IComparable<T>.CompareTo here.
 437         // We can avoid boxing for value type and casting for reference types.
 438         private static int BinarySearch(T[] array, int index, int length, T value)
 439         {
 440             int lo = index;
 441             int hi = index + length - 1;
 442             while (lo <= hi)
 443             {
 444                 int i = lo + ((hi - lo) >> 1);
 445                 int order;
 446                 if (array[i] == null)
 447                 {
 448                     order = (value == null) ? 0 : -1;
 449                 }
 450                 else
 451                 {
 452                     order = array[i].CompareTo(value);
 453                 }
 454
 455                 if (order == 0)
 456                 {
 457                     return i;
 458                 }
 459
 460                 if (order < 0)
 461                 {
 462                     lo = i + 1;
 463                 }
 464                 else
 465                 {
 466                     hi = i - 1;
 467                 }
 468             }
 469
 470             return ~lo;
 471         }
 472
 473         private static void SwapIfGreaterWithItems(T[] keys, int a, int b)
 474         {
 475             Contract.Requires(keys != null);
 476             Contract.Requires(0 <= a && a < keys.Length);
 477             Contract.Requires(0 <= b && b < keys.Length);
 478
 479             if (a != b)
 480             {
 481                 if (keys[a] != null && keys[a].CompareTo(keys[b]) > 0)
 482                 {
 483                     T key = keys[a];
 484                     keys[a] = keys[b];
 485                     keys[b] = key;
 486                 }
 487             }
 488         }
 489
 490         private static void Swap(T[] a, int i, int j)
 491         {
 492             if (i != j)
 493             {
 494                 T t = a[i];
 495                 a[i] = a[j];
 496                 a[j] = t;
 497             }
 498         }
 499
 500         internal static void IntrospectiveSort(T[] keys, int left, int length)
 501         {
 502             Contract.Requires(keys != null);
 503             Contract.Requires(left >= 0);
 504             Contract.Requires(length >= 0);
 505             Contract.Requires(length <= keys.Length);
 506             Contract.Requires(length + left <= keys.Length);
 507
 508             if (length < 2)
 509                 return;
 510
 511             IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));
 512         }
 513
 514         private static void IntroSort(T[] keys, int lo, int hi, int depthLimit)
 515         {
 516             Contract.Requires(keys != null);
 517             Contract.Requires(lo >= 0);
 518             Contract.Requires(hi < keys.Length);
 519
 520             while (hi > lo)
 521             {
 522                 int partitionSize = hi - lo + 1;
 523                 if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
 524                 {
 525                     if (partitionSize == 1)
 526                     {
 527                         return;
 528                     }
 529                     if (partitionSize == 2)
 530                     {
 531                         SwapIfGreaterWithItems(keys, lo, hi);
 532                         return;
 533                     }
 534                     if (partitionSize == 3)
 535                     {
 536                         SwapIfGreaterWithItems(keys, lo, hi - 1);
 537                         SwapIfGreaterWithItems(keys, lo, hi);
 538                         SwapIfGreaterWithItems(keys, hi - 1, hi);
 539                         return;
 540                     }
 541
 542                     InsertionSort(keys, lo, hi);
 543                     return;
 544                 }
 545
 546                 if (depthLimit == 0)
 547                 {
 548                     Heapsort(keys, lo, hi);
 549                     return;
 550                 }
 551                 depthLimit--;
 552
 553                 int p = PickPivotAndPartition(keys, lo, hi);
 554                 // Note we've already partitioned around the pivot and do not have to move the pivot again.
 555                 IntroSort(keys, p + 1, hi, depthLimit);
 556                 hi = p - 1;
 557             }
 558         }
 559
 560         private static int PickPivotAndPartition(T[] keys, int lo, int hi)
 561         {
 562             Contract.Requires(keys != null);
 563             Contract.Requires(lo >= 0);
 564             Contract.Requires(hi > lo);
 565             Contract.Requires(hi < keys.Length);
 566             Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi);
 567
 568             // Compute median-of-three.  But also partition them, since we've done the comparison.
 569             int middle = lo + ((hi - lo) / 2);
 570
 571             // Sort lo, mid and hi appropriately, then pick mid as the pivot.
 572             SwapIfGreaterWithItems(keys, lo, middle);  // swap the low with the mid point
 573             SwapIfGreaterWithItems(keys, lo, hi);   // swap the low with the high
 574             SwapIfGreaterWithItems(keys, middle, hi); // swap the middle with the high
 575
 576             T pivot = keys[middle];
 577             Swap(keys, middle, hi - 1);
 578             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.
 579
 580             while (left < right)
 581             {
 582                 if (pivot == null)
 583                 {
 584                     while (left < (hi - 1) && keys[++left] == null) ;
 585                     while (right > lo && keys[--right] != null) ;
 586                 }
 587                 else
 588                 {
 589                     while (pivot.CompareTo(keys[++left]) > 0) ;
 590                     while (pivot.CompareTo(keys[--right]) < 0) ;
 591                 }
 592
 593                 if (left >= right)
 594                     break;
 595
 596                 Swap(keys, left, right);
 597             }
 598
 599             // Put pivot in the right location.
 600             Swap(keys, left, (hi - 1));
 601             return left;
 602         }
 603
 604         private static void Heapsort(T[] keys, int lo, int hi)
 605         {
 606             Contract.Requires(keys != null);
 607             Contract.Requires(lo >= 0);
 608             Contract.Requires(hi > lo);
 609             Contract.Requires(hi < keys.Length);
 610
 611             int n = hi - lo + 1;
 612             for (int i = n / 2; i >= 1; i = i - 1)
 613             {
 614                 DownHeap(keys, i, n, lo);
 615             }
 616             for (int i = n; i > 1; i = i - 1)
 617             {
 618                 Swap(keys, lo, lo + i - 1);
 619                 DownHeap(keys, 1, i - 1, lo);
 620             }
 621         }
 622
 623         private static void DownHeap(T[] keys, int i, int n, int lo)
 624         {
 625             Contract.Requires(keys != null);
 626             Contract.Requires(lo >= 0);
 627             Contract.Requires(lo < keys.Length);
 628
 629             T d = keys[lo + i - 1];
 630             int child;
 631             while (i <= n / 2)
 632             {
 633                 child = 2 * i;
 634                 if (child < n && (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(keys[lo + child]) < 0))
 635                 {
 636                     child++;
 637                 }
 638                 if (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(d) < 0)
 639                     break;
 640                 keys[lo + i - 1] = keys[lo + child - 1];
 641                 i = child;
 642             }
 643             keys[lo + i - 1] = d;
 644         }
 645
 646         private static void InsertionSort(T[] keys, int lo, int hi)
 647         {
 648             Contract.Requires(keys != null);
 649             Contract.Requires(lo >= 0);
 650             Contract.Requires(hi >= lo);
 651             Contract.Requires(hi <= keys.Length);
 652
 653             int i, j;
 654             T t;
 655             for (i = lo; i < hi; i++)
 656             {
 657                 j = i;
 658                 t = keys[i + 1];
 659                 while (j >= lo && (t == null || t.CompareTo(keys[j]) < 0))
 660                 {
 661                     keys[j + 1] = keys[j];
 662                     j--;
 663                 }
 664                 keys[j + 1] = t;
 665             }
 666         }
 667     }
 668
 669     #endregion
 670
 671     #region ArraySortHelper for paired key and value arrays
 672
 673     internal interface IArraySortHelper<TKey, TValue>
 674     {
 675         void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer);
 676     }
 677
 678     [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`2")]
 679     internal class ArraySortHelper<TKey, TValue>
 680         : IArraySortHelper<TKey, TValue>
 681     {
 682         private static volatile IArraySortHelper<TKey, TValue> defaultArraySortHelper;
 683
 684         public static IArraySortHelper<TKey, TValue> Default
 685         {
 686             get
 687             {
 688                 IArraySortHelper<TKey, TValue> sorter = defaultArraySortHelper;
 689                 if (sorter == null)
 690                     sorter = CreateArraySortHelper();
 691
 692                 return sorter;
 693             }
 694         }
 695
 696         private static IArraySortHelper<TKey, TValue> CreateArraySortHelper()
 697         {
 698 #if !MONO
 699             if (typeof(IComparable<TKey>).IsAssignableFrom(typeof(TKey)))
 700             {
 701                 defaultArraySortHelper = (IArraySortHelper<TKey, TValue>)RuntimeTypeHandle.Allocate(typeof(GenericArraySortHelper<string, string>).TypeHandle.Instantiate(new Type[] { typeof(TKey), typeof(TValue) }));
 702             }
 703             else
 704 #endif
 705             {
 706                 defaultArraySortHelper = new ArraySortHelper<TKey, TValue>();
 707             }
 708             return defaultArraySortHelper;
 709         }
 710
 711         public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer)
 712         {
 713             Debug.Assert(keys != null, "Check the arguments in the caller!");  // Precondition on interface method
 714             Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
 715
 716             // Add a try block here to detect IComparers (or their
 717             // underlying IComparables, etc) that are bogus.
 718             try
 719             {
 720                 if (comparer == null || comparer == Comparer<TKey>.Default)
 721                 {
 722                     comparer = Comparer<TKey>.Default;
 723                 }
 724
 725                 IntrospectiveSort(keys, values, index, length, comparer);
 726             }
 727             catch (IndexOutOfRangeException)
 728             {
 729                 IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
 730             }
 731             catch (Exception e)
 732             {
 733                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
 734             }
 735         }
 736
 737         private static void SwapIfGreaterWithItems(TKey[] keys, TValue[] values, IComparer<TKey> comparer, int a, int b)
 738         {
 739             Contract.Requires(keys != null);
 740             Contract.Requires(values == null || values.Length >= keys.Length);
 741             Contract.Requires(comparer != null);
 742             Contract.Requires(0 <= a && a < keys.Length);
 743             Contract.Requires(0 <= b && b < keys.Length);
 744
 745             if (a != b)
 746             {
 747                 if (comparer.Compare(keys[a], keys[b]) > 0)
 748                 {
 749                     TKey key = keys[a];
 750                     keys[a] = keys[b];
 751                     keys[b] = key;
 752                     if (values != null)
 753                     {
 754                         TValue value = values[a];
 755                         values[a] = values[b];
 756                         values[b] = value;
 757                     }
 758                 }
 759             }
 760         }
 761
 762         private static void Swap(TKey[] keys, TValue[] values, int i, int j)
 763         {
 764             if (i != j)
 765             {
 766                 TKey k = keys[i];
 767                 keys[i] = keys[j];
 768                 keys[j] = k;
 769                 if (values != null)
 770                 {
 771                     TValue v = values[i];
 772                     values[i] = values[j];
 773                     values[j] = v;
 774                 }
 775             }
 776         }
 777
 778         internal static void IntrospectiveSort(TKey[] keys, TValue[] values, int left, int length, IComparer<TKey> comparer)
 779         {
 780             Contract.Requires(keys != null);
 781             Contract.Requires(values != null);
 782             Contract.Requires(comparer != null);
 783             Contract.Requires(left >= 0);
 784             Contract.Requires(length >= 0);
 785             Contract.Requires(length <= keys.Length);
 786             Contract.Requires(length + left <= keys.Length);
 787             Contract.Requires(length + left <= values.Length);
 788
 789             if (length < 2)
 790                 return;
 791
 792             IntroSort(keys, values, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer);
 793         }
 794
 795         private static void IntroSort(TKey[] keys, TValue[] values, int lo, int hi, int depthLimit, IComparer<TKey> comparer)
 796         {
 797             Contract.Requires(keys != null);
 798             Contract.Requires(values != null);
 799             Contract.Requires(comparer != null);
 800             Contract.Requires(lo >= 0);
 801             Contract.Requires(hi < keys.Length);
 802
 803             while (hi > lo)
 804             {
 805                 int partitionSize = hi - lo + 1;
 806                 if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
 807                 {
 808                     if (partitionSize == 1)
 809                     {
 810                         return;
 811                     }
 812                     if (partitionSize == 2)
 813                     {
 814                         SwapIfGreaterWithItems(keys, values, comparer, lo, hi);
 815                         return;
 816                     }
 817                     if (partitionSize == 3)
 818                     {
 819                         SwapIfGreaterWithItems(keys, values, comparer, lo, hi - 1);
 820                         SwapIfGreaterWithItems(keys, values, comparer, lo, hi);
 821                         SwapIfGreaterWithItems(keys, values, comparer, hi - 1, hi);
 822                         return;
 823                     }
 824
 825                     InsertionSort(keys, values, lo, hi, comparer);
 826                     return;
 827                 }
 828
 829                 if (depthLimit == 0)
 830                 {
 831                     Heapsort(keys, values, lo, hi, comparer);
 832                     return;
 833                 }
 834                 depthLimit--;
 835
 836                 int p = PickPivotAndPartition(keys, values, lo, hi, comparer);
 837                 // Note we've already partitioned around the pivot and do not have to move the pivot again.
 838                 IntroSort(keys, values, p + 1, hi, depthLimit, comparer);
 839                 hi = p - 1;
 840             }
 841         }
 842
 843         private static int PickPivotAndPartition(TKey[] keys, TValue[] values, int lo, int hi, IComparer<TKey> comparer)
 844         {
 845             Contract.Requires(keys != null);
 846             Contract.Requires(values != null);
 847             Contract.Requires(comparer != null);
 848             Contract.Requires(lo >= 0);
 849             Contract.Requires(hi > lo);
 850             Contract.Requires(hi < keys.Length);
 851             Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi);
 852
 853             // Compute median-of-three.  But also partition them, since we've done the comparison.
 854             int middle = lo + ((hi - lo) / 2);
 855
 856             // Sort lo, mid and hi appropriately, then pick mid as the pivot.
 857             SwapIfGreaterWithItems(keys, values, comparer, lo, middle);  // swap the low with the mid point
 858             SwapIfGreaterWithItems(keys, values, comparer, lo, hi);   // swap the low with the high
 859             SwapIfGreaterWithItems(keys, values, comparer, middle, hi); // swap the middle with the high
 860
 861             TKey pivot = keys[middle];
 862             Swap(keys, values, middle, hi - 1);
 863             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.
 864
 865             while (left < right)
 866             {
 867                 while (comparer.Compare(keys[++left], pivot) < 0) ;
 868                 while (comparer.Compare(pivot, keys[--right]) < 0) ;
 869
 870                 if (left >= right)
 871                     break;
 872
 873                 Swap(keys, values, left, right);
 874             }
 875
 876             // Put pivot in the right location.
 877             Swap(keys, values, left, (hi - 1));
 878             return left;
 879         }
 880
 881         private static void Heapsort(TKey[] keys, TValue[] values, int lo, int hi, IComparer<TKey> comparer)
 882         {
 883             Contract.Requires(keys != null);
 884             Contract.Requires(values != null);
 885             Contract.Requires(comparer != null);
 886             Contract.Requires(lo >= 0);
 887             Contract.Requires(hi > lo);
 888             Contract.Requires(hi < keys.Length);
 889
 890             int n = hi - lo + 1;
 891             for (int i = n / 2; i >= 1; i = i - 1)
 892             {
 893                 DownHeap(keys, values, i, n, lo, comparer);
 894             }
 895             for (int i = n; i > 1; i = i - 1)
 896             {
 897                 Swap(keys, values, lo, lo + i - 1);
 898                 DownHeap(keys, values, 1, i - 1, lo, comparer);
 899             }
 900         }
 901
 902         private static void DownHeap(TKey[] keys, TValue[] values, int i, int n, int lo, IComparer<TKey> comparer)
 903         {
 904             Contract.Requires(keys != null);
 905             Contract.Requires(comparer != null);
 906             Contract.Requires(lo >= 0);
 907             Contract.Requires(lo < keys.Length);
 908
 909             TKey d = keys[lo + i - 1];
 910             TValue dValue = (values != null) ? values[lo + i - 1] : default(TValue);
 911             int child;
 912             while (i <= n / 2)
 913             {
 914                 child = 2 * i;
 915                 if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0)
 916                 {
 917                     child++;
 918                 }
 919                 if (!(comparer.Compare(d, keys[lo + child - 1]) < 0))
 920                     break;
 921                 keys[lo + i - 1] = keys[lo + child - 1];
 922                 if (values != null)
 923                     values[lo + i - 1] = values[lo + child - 1];
 924                 i = child;
 925             }
 926             keys[lo + i - 1] = d;
 927             if (values != null)
 928                 values[lo + i - 1] = dValue;
 929         }
 930
 931         private static void InsertionSort(TKey[] keys, TValue[] values, int lo, int hi, IComparer<TKey> comparer)
 932         {
 933             Contract.Requires(keys != null);
 934             Contract.Requires(values != null);
 935             Contract.Requires(comparer != null);
 936             Contract.Requires(lo >= 0);
 937             Contract.Requires(hi >= lo);
 938             Contract.Requires(hi <= keys.Length);
 939
 940             int i, j;
 941             TKey t;
 942             TValue tValue;
 943             for (i = lo; i < hi; i++)
 944             {
 945                 j = i;
 946                 t = keys[i + 1];
 947                 tValue = (values != null) ? values[i + 1] : default(TValue);
 948                 while (j >= lo && comparer.Compare(t, keys[j]) < 0)
 949                 {
 950                     keys[j + 1] = keys[j];
 951                     if (values != null)
 952                         values[j + 1] = values[j];
 953                     j--;
 954                 }
 955                 keys[j + 1] = t;
 956                 if (values != null)
 957                     values[j + 1] = tValue;
 958             }
 959         }
 960     }
 961
 962     internal class GenericArraySortHelper<TKey, TValue>
 963         : IArraySortHelper<TKey, TValue>
 964         where TKey : IComparable<TKey>
 965     {
 966         public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer)
 967         {
 968             Debug.Assert(keys != null, "Check the arguments in the caller!");
 969             Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
 970
 971             // Add a try block here to detect IComparers (or their
 972             // underlying IComparables, etc) that are bogus.
 973             try
 974             {
 975                 if (comparer == null || comparer == Comparer<TKey>.Default)
 976                 {
 977                     IntrospectiveSort(keys, values, index, length);
 978                 }
 979                 else
 980                 {
 981                     ArraySortHelper<TKey, TValue>.IntrospectiveSort(keys, values, index, length, comparer);
 982                 }
 983             }
 984             catch (IndexOutOfRangeException)
 985             {
 986                 IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
 987             }
 988             catch (Exception e)
 989             {
 990                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
 991             }
 992         }
 993
 994         private static void SwapIfGreaterWithItems(TKey[] keys, TValue[] values, int a, int b)
 995         {
 996             if (a != b)
 997             {
 998                 if (keys[a] != null && keys[a].CompareTo(keys[b]) > 0)
 999                 {
1000                     TKey key = keys[a];
1001                     keys[a] = keys[b];
1002                     keys[b] = key;
1003                     if (values != null)
1004                     {
1005                         TValue value = values[a];
1006                         values[a] = values[b];
1007                         values[b] = value;
1008                     }
1009                 }
1010             }
1011         }
1012
1013         private static void Swap(TKey[] keys, TValue[] values, int i, int j)
1014         {
1015             if (i != j)
1016             {
1017                 TKey k = keys[i];
1018                 keys[i] = keys[j];
1019                 keys[j] = k;
1020                 if (values != null)
1021                 {
1022                     TValue v = values[i];
1023                     values[i] = values[j];
1024                     values[j] = v;
1025                 }
1026             }
1027         }
1028
1029         internal static void IntrospectiveSort(TKey[] keys, TValue[] values, int left, int length)
1030         {
1031             Contract.Requires(keys != null);
1032             Contract.Requires(values != null);
1033             Contract.Requires(left >= 0);
1034             Contract.Requires(length >= 0);
1035             Contract.Requires(length <= keys.Length);
1036             Contract.Requires(length + left <= keys.Length);
1037             Contract.Requires(length + left <= values.Length);
1038
1039             if (length < 2)
1040                 return;
1041
1042             IntroSort(keys, values, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));
1043         }
1044
1045         private static void IntroSort(TKey[] keys, TValue[] values, int lo, int hi, int depthLimit)
1046         {
1047             Contract.Requires(keys != null);
1048             Contract.Requires(values != null);
1049             Contract.Requires(lo >= 0);
1050             Contract.Requires(hi < keys.Length);
1051
1052             while (hi > lo)
1053             {
1054                 int partitionSize = hi - lo + 1;
1055                 if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
1056                 {
1057                     if (partitionSize == 1)
1058                     {
1059                         return;
1060                     }
1061                     if (partitionSize == 2)
1062                     {
1063                         SwapIfGreaterWithItems(keys, values, lo, hi);
1064                         return;
1065                     }
1066                     if (partitionSize == 3)
1067                     {
1068                         SwapIfGreaterWithItems(keys, values, lo, hi - 1);
1069                         SwapIfGreaterWithItems(keys, values, lo, hi);
1070                         SwapIfGreaterWithItems(keys, values, hi - 1, hi);
1071                         return;
1072                     }
1073
1074                     InsertionSort(keys, values, lo, hi);
1075                     return;
1076                 }
1077
1078                 if (depthLimit == 0)
1079                 {
1080                     Heapsort(keys, values, lo, hi);
1081                     return;
1082                 }
1083                 depthLimit--;
1084
1085                 int p = PickPivotAndPartition(keys, values, lo, hi);
1086                 // Note we've already partitioned around the pivot and do not have to move the pivot again.
1087                 IntroSort(keys, values, p + 1, hi, depthLimit);
1088                 hi = p - 1;
1089             }
1090         }
1091
1092         private static int PickPivotAndPartition(TKey[] keys, TValue[] values, int lo, int hi)
1093         {
1094             Contract.Requires(keys != null);
1095             Contract.Requires(values != null);
1096             Contract.Requires(lo >= 0);
1097             Contract.Requires(hi > lo);
1098             Contract.Requires(hi < keys.Length);
1099             Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi);
1100
1101             // Compute median-of-three.  But also partition them, since we've done the comparison.
1102             int middle = lo + ((hi - lo) / 2);
1103
1104             // Sort lo, mid and hi appropriately, then pick mid as the pivot.
1105             SwapIfGreaterWithItems(keys, values, lo, middle);  // swap the low with the mid point
1106             SwapIfGreaterWithItems(keys, values, lo, hi);   // swap the low with the high
1107             SwapIfGreaterWithItems(keys, values, middle, hi); // swap the middle with the high
1108
1109             TKey pivot = keys[middle];
1110             Swap(keys, values, middle, hi - 1);
1111             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.
1112
1113             while (left < right)
1114             {
1115                 if (pivot == null)
1116                 {
1117                     while (left < (hi - 1) && keys[++left] == null) ;
1118                     while (right > lo && keys[--right] != null) ;
1119                 }
1120                 else
1121                 {
1122                     while (pivot.CompareTo(keys[++left]) > 0) ;
1123                     while (pivot.CompareTo(keys[--right]) < 0) ;
1124                 }
1125
1126                 if (left >= right)
1127                     break;
1128
1129                 Swap(keys, values, left, right);
1130             }
1131
1132             // Put pivot in the right location.
1133             Swap(keys, values, left, (hi - 1));
1134             return left;
1135         }
1136
1137         private static void Heapsort(TKey[] keys, TValue[] values, int lo, int hi)
1138         {
1139             Contract.Requires(keys != null);
1140             Contract.Requires(values != null);
1141             Contract.Requires(lo >= 0);
1142             Contract.Requires(hi > lo);
1143             Contract.Requires(hi < keys.Length);
1144
1145             int n = hi - lo + 1;
1146             for (int i = n / 2; i >= 1; i = i - 1)
1147             {
1148                 DownHeap(keys, values, i, n, lo);
1149             }
1150             for (int i = n; i > 1; i = i - 1)
1151             {
1152                 Swap(keys, values, lo, lo + i - 1);
1153                 DownHeap(keys, values, 1, i - 1, lo);
1154             }
1155         }
1156
1157         private static void DownHeap(TKey[] keys, TValue[] values, int i, int n, int lo)
1158         {
1159             Contract.Requires(keys != null);
1160             Contract.Requires(lo >= 0);
1161             Contract.Requires(lo < keys.Length);
1162
1163             TKey d = keys[lo + i - 1];
1164             TValue dValue = (values != null) ? values[lo + i - 1] : default(TValue);
1165             int child;
1166             while (i <= n / 2)
1167             {
1168                 child = 2 * i;
1169                 if (child < n && (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(keys[lo + child]) < 0))
1170                 {
1171                     child++;
1172                 }
1173                 if (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(d) < 0)
1174                     break;
1175                 keys[lo + i - 1] = keys[lo + child - 1];
1176                 if (values != null)
1177                     values[lo + i - 1] = values[lo + child - 1];
1178                 i = child;
1179             }
1180             keys[lo + i - 1] = d;
1181             if (values != null)
1182                 values[lo + i - 1] = dValue;
1183         }
1184
1185         private static void InsertionSort(TKey[] keys, TValue[] values, int lo, int hi)
1186         {
1187             Contract.Requires(keys != null);
1188             Contract.Requires(values != null);
1189             Contract.Requires(lo >= 0);
1190             Contract.Requires(hi >= lo);
1191             Contract.Requires(hi <= keys.Length);
1192
1193             int i, j;
1194             TKey t;
1195             TValue tValue;
1196             for (i = lo; i < hi; i++)
1197             {
1198                 j = i;
1199                 t = keys[i + 1];
1200                 tValue = (values != null) ? values[i + 1] : default(TValue);
1201                 while (j >= lo && (t == null || t.CompareTo(keys[j]) < 0))
1202                 {
1203                     keys[j + 1] = keys[j];
1204                     if (values != null)
1205                         values[j + 1] = values[j];
1206                     j--;
1207                 }
1208                 keys[j + 1] = t;
1209                 if (values != null)
1210                     values[j + 1] = tValue;
1211             }
1212         }
1213     }
1214
1215     #endregion
1216 }