mcs/class/referencesource/mscorlib/system/collections/generic/arraysorthelper.cs

   1 // ==++==
   2 //
   3 //   Copyright (c) Microsoft Corporation.  All rights reserved.
   4 //
   5 // ==--==
   6 /*============================================================
   7 **
   8 ** Class:  ArraySortHelper
   9 **
  10 ** <OWNER>Microsoft</OWNER>
  11 **
  12 **
  13 ** Purpose: class to sort arrays
  14 **
  15 **
  16 ===========================================================*/
  17 namespace System.Collections.Generic
  18 {
  19     using System;
  20     using System.Globalization;
  21     using System.Runtime.CompilerServices;
  22     using System.Diagnostics.Contracts;
  23     using System.Runtime.Versioning;
  24
  25     #region ArraySortHelper for single arrays
  26
  27 #if CONTRACTS_FULL
  28     [ContractClass(typeof(IArraySortHelperContract<>))]
  29 #endif // CONTRACTS_FULL
  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 #if CONTRACTS_FULL
  37     [ContractClassFor(typeof(IArraySortHelper<>))]
  38     internal abstract class IArraySortHelperContract<TKey> : IArraySortHelper<TKey>
  39     {
  40         void IArraySortHelper<TKey>.Sort(TKey[] keys, int index, int length, IComparer<TKey> comparer)
  41         {
  42             Contract.Requires(keys != null, "Check the arguments in the caller!");
  43             Contract.Requires(index >= 0 && index <= keys.Length);  // allow 0?
  44             Contract.Requires(length >= 0 && index + length <= keys.Length);
  45         }
  46
  47         int IArraySortHelper<TKey>.BinarySearch(TKey[] keys, int index, int length, TKey value, IComparer<TKey> comparer)
  48         {
  49             Contract.Requires(index >= 0 && index <= keys.Length);  // allow 0?
  50             Contract.Requires(length >= 0 && index + length <= keys.Length);
  51             Contract.Ensures((Contract.Result<int>() >= index && Contract.Result<int>() <= index + length) ||
  52                 (~Contract.Result<int>() >= index && ~Contract.Result<int>() <= index + length), "Binary search returned a bad value");
  53
  54             return default(int);
  55         }
  56     }
  57 #endif // CONTRACTS_FULL
  58
  59     internal static class IntrospectiveSortUtilities
  60     {
  61         // This is the threshold where Introspective sort switches to Insertion sort.
  62         // Imperically, 16 seems to speed up most cases without slowing down others, at least for integers.
  63         // Large value types may benefit from a smaller number.
  64         internal const int IntrosortSizeThreshold = 16;
  65
  66         internal const int QuickSortDepthThreshold = 32;
  67
  68         internal static int FloorLog2(int n)
  69         {
  70             int result = 0;
  71             while (n >= 1)
  72             {
  73                 result++;
  74                 n = n / 2;
  75             }
  76             return result;
  77         }
  78
  79         internal static void ThrowOrIgnoreBadComparer(Object comparer) {
  80             // This is hit when an invarant of QuickSort is violated due to a bad IComparer implementation (for
  81             // example, imagine an IComparer that returns 0 when items are equal but -1 all other times).
  82             //
  83             // We could have thrown this exception on v4, but due to changes in v4.5 around how we partition arrays
  84             // there are different sets of input where we would throw this exception.  In order to reduce overall risk from
  85             // an app compat persective, we're changing to never throw on v4.  Instead, we'll return with a partially
  86             // sorted array.
  87             if(BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) {
  88                 throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", comparer));
  89             }
  90         }
  91
  92     }
  93
  94     [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`1")]
  95     internal class ArraySortHelper<T>
  96         : IArraySortHelper<T>
  97     {
  98         static volatile IArraySortHelper<T> defaultArraySortHelper;
  99
 100         public static IArraySortHelper<T> Default
 101         {
 102             get
 103             {
 104                 IArraySortHelper<T> sorter = defaultArraySortHelper;
 105                 if (sorter == null)
 106                     sorter = CreateArraySortHelper();
 107
 108                 return sorter;
 109             }
 110         }
 111
 112         [System.Security.SecuritySafeCritical]  // auto-generated
 113         private static IArraySortHelper<T> CreateArraySortHelper()
 114         {
 115             if (typeof(IComparable<T>).IsAssignableFrom(typeof(T)))
 116             {
 117                 defaultArraySortHelper = (IArraySortHelper<T>)RuntimeTypeHandle.Allocate(typeof(GenericArraySortHelper<string>).TypeHandle.Instantiate(new Type[] { typeof(T) }));
 118             }
 119             else
 120             {
 121                 defaultArraySortHelper = new ArraySortHelper<T>();
 122             }
 123             return defaultArraySortHelper;
 124         }
 125
 126         #region IArraySortHelper<T> Members
 127
 128         public void Sort(T[] keys, int index, int length, IComparer<T> comparer)
 129         {
 130             Contract.Assert(keys != null, "Check the arguments in the caller!");
 131             Contract.Assert( index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
 132
 133             // Add a try block here to detect IComparers (or their
 134             // underlying IComparables, etc) that are bogus.
 135             try
 136             {
 137                 if (comparer == null)
 138                 {
 139                     comparer = Comparer<T>.Default;
 140                 }
 141
 142 #if FEATURE_CORECLR
 143                 // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade
 144                 // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka
 145                 // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
 146
 147                 IntrospectiveSort(keys, index, length, comparer);
 148 #else
 149                 if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
 150                 {
 151                     IntrospectiveSort(keys, index, length, comparer);
 152                 }
 153                 else
 154                 {
 155                     DepthLimitedQuickSort(keys, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold);
 156                 }
 157 #endif
 158             }
 159             catch (IndexOutOfRangeException)
 160             {
 161                 IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
 162             }
 163             catch (Exception e)
 164             {
 165                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
 166             }
 167         }
 168
 169         public int BinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
 170         {
 171             try
 172             {
 173                 if (comparer == null)
 174                 {
 175                     comparer = Comparer<T>.Default;
 176                 }
 177
 178                 return InternalBinarySearch(array, index, length, value, comparer);
 179             }
 180             catch (Exception e)
 181             {
 182                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
 183             }
 184         }
 185
 186         #endregion
 187
 188         internal static int InternalBinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
 189         {
 190             Contract.Requires(array != null, "Check the arguments in the caller!");
 191             Contract.Requires(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!");
 192
 193             int lo = index;
 194             int hi = index + length - 1;
 195             while (lo <= hi)
 196             {
 197                 int i = lo + ((hi - lo) >> 1);
 198                 int order = comparer.Compare(array[i], value);
 199
 200                 if (order == 0) return i;
 201                 if (order < 0)
 202                 {
 203                     lo = i + 1;
 204                 }
 205                 else
 206                 {
 207                     hi = i - 1;
 208                 }
 209             }
 210
 211             return ~lo;
 212         }
 213
 214         private static void SwapIfGreater(T[] keys, IComparer<T> comparer, int a, int b)
 215         {
 216             if (a != b)
 217             {
 218                 if (comparer.Compare(keys[a], keys[b]) > 0)
 219                 {
 220                     T key = keys[a];
 221                     keys[a] = keys[b];
 222                     keys[b] = key;
 223                 }
 224             }
 225         }
 226
 227         private static void Swap(T[] a, int i, int j)
 228         {
 229             if(i != j)
 230             {
 231                 T t = a[i];
 232                 a[i] = a[j];
 233                 a[j] = t;
 234             }
 235         }
 236
 237         internal static void DepthLimitedQuickSort(T[] keys, int left, int right, IComparer<T> comparer, int depthLimit)
 238         {
 239             do
 240             {
 241                 if (depthLimit == 0)
 242                 {
 243                     Heapsort(keys, left, right, comparer);
 244                     return;
 245                 }
 246
 247                 int i = left;
 248                 int j = right;
 249
 250                 // pre-sort the low, middle (pivot), and high values in place.
 251                 // this improves performance in the face of already sorted data, or
 252                 // data that is made up of multiple sorted runs appended together.
 253                 int middle = i + ((j - i) >> 1);
 254                 SwapIfGreater(keys, comparer, i, middle);  // swap the low with the mid point
 255                 SwapIfGreater(keys, comparer, i, j);   // swap the low with the high
 256                 SwapIfGreater(keys, comparer, middle, j); // swap the middle with the high
 257
 258                 T x = keys[middle];
 259                 do
 260                 {
 261                     while (comparer.Compare(keys[i], x) < 0) i++;
 262                     while (comparer.Compare(x, keys[j]) < 0) j--;
 263                     Contract.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?");
 264                     if (i > j) break;
 265                     if (i < j)
 266                     {
 267                         T key = keys[i];
 268                         keys[i] = keys[j];
 269                         keys[j] = key;
 270                     }
 271                     i++;
 272                     j--;
 273                 } while (i <= j);
 274
 275                 // The next iteration of the while loop is to "recursively" sort the larger half of the array and the
 276                 // following calls recrusively sort the smaller half.  So we subtrack one from depthLimit here so
 277                 // both sorts see the new value.
 278                 depthLimit--;
 279
 280                 if (j - left <= right - i)
 281                 {
 282                     if (left < j) DepthLimitedQuickSort(keys, left, j, comparer, depthLimit);
 283                     left = i;
 284                 }
 285                 else
 286                 {
 287                     if (i < right) DepthLimitedQuickSort(keys, i, right, comparer, depthLimit);
 288                     right = j;
 289                 }
 290             } while (left < right);
 291         }
 292
 293         internal static void IntrospectiveSort(T[] keys, int left, int length, IComparer<T> comparer)
 294         {
 295             Contract.Requires(keys != null);
 296             Contract.Requires(comparer != null);
 297             Contract.Requires(left >= 0);
 298             Contract.Requires(length >= 0);
 299             Contract.Requires(length <= keys.Length);
 300             Contract.Requires(length + left <= keys.Length);
 301
 302             if (length < 2)
 303                 return;
 304
 305             IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer);
 306         }
 307
 308         private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, IComparer<T> comparer)
 309         {
 310             Contract.Requires(keys != null);
 311             Contract.Requires(comparer != null);
 312             Contract.Requires(lo >= 0);
 313             Contract.Requires(hi < keys.Length);
 314
 315             while (hi > lo)
 316             {
 317                 int partitionSize = hi - lo + 1;
 318                 if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
 319                 {
 320                     if (partitionSize == 1)
 321                     {
 322                         return;
 323                     }
 324                     if (partitionSize == 2)
 325                     {
 326                         SwapIfGreater(keys, comparer, lo, hi);
 327                         return;
 328                     }
 329                     if (partitionSize == 3)
 330                     {
 331                         SwapIfGreater(keys, comparer, lo, hi-1);
 332                         SwapIfGreater(keys, comparer, lo, hi);
 333                         SwapIfGreater(keys, comparer, hi-1, hi);
 334                         return;
 335                     }
 336
 337                     InsertionSort(keys, lo, hi, comparer);
 338                     return;
 339                 }
 340
 341                 if (depthLimit == 0)
 342                 {
 343                     Heapsort(keys, lo, hi, comparer);
 344                     return;
 345                 }
 346                 depthLimit--;
 347
 348                 int p = PickPivotAndPartition(keys, lo, hi, comparer);
 349                 // Note we've already partitioned around the pivot and do not have to move the pivot again.
 350                 IntroSort(keys, p + 1, hi, depthLimit, comparer);
 351                 hi = p - 1;
 352             }
 353         }
 354
 355         private static int PickPivotAndPartition(T[] keys, int lo, int hi, IComparer<T> comparer)
 356         {
 357             Contract.Requires(keys != null);
 358             Contract.Requires(comparer != null);
 359             Contract.Requires(lo >= 0);
 360             Contract.Requires(hi > lo);
 361             Contract.Requires(hi < keys.Length);
 362             Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi);
 363
 364             // Compute median-of-three.  But also partition them, since we've done the comparison.
 365             int middle = lo + ((hi - lo) / 2);
 366
 367             // Sort lo, mid and hi appropriately, then pick mid as the pivot.
 368             SwapIfGreater(keys, comparer, lo, middle);  // swap the low with the mid point
 369             SwapIfGreater(keys, comparer, lo, hi);   // swap the low with the high
 370             SwapIfGreater(keys, comparer, middle, hi); // swap the middle with the high
 371
 372             T pivot = keys[middle];
 373             Swap(keys, middle, hi - 1);
 374             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.
 375
 376             while (left < right)
 377             {
 378                 while (comparer.Compare(keys[++left], pivot) < 0) ;
 379                 while (comparer.Compare(pivot, keys[--right]) < 0) ;
 380
 381                 if (left >= right)
 382                     break;
 383
 384                 Swap(keys, left, right);
 385             }
 386
 387             // Put pivot in the right location.
 388             Swap(keys, left, (hi - 1));
 389             return left;
 390         }
 391
 392         private static void Heapsort(T[] keys, int lo, int hi, IComparer<T> comparer)
 393         {
 394             Contract.Requires(keys != null);
 395             Contract.Requires(comparer != null);
 396             Contract.Requires(lo >= 0);
 397             Contract.Requires(hi > lo);
 398             Contract.Requires(hi < keys.Length);
 399
 400             int n = hi - lo + 1;
 401             for (int i = n / 2; i >= 1; i = i - 1)
 402             {
 403                 DownHeap(keys, i, n, lo, comparer);
 404             }
 405             for (int i = n; i > 1; i = i - 1)
 406             {
 407                 Swap(keys, lo, lo + i - 1);
 408                 DownHeap(keys, 1, i - 1, lo, comparer);
 409             }
 410         }
 411
 412         private static void DownHeap(T[] keys, int i, int n, int lo, IComparer<T> comparer)
 413         {
 414             Contract.Requires(keys != null);
 415             Contract.Requires(comparer != null);
 416             Contract.Requires(lo >= 0);
 417             Contract.Requires(lo < keys.Length);
 418
 419             T d = keys[lo + i - 1];
 420             int child;
 421             while (i <= n / 2)
 422             {
 423                 child = 2 * i;
 424                 if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0)
 425                 {
 426                     child++;
 427                 }
 428                 if (!(comparer.Compare(d, keys[lo + child - 1]) < 0))
 429                     break;
 430                 keys[lo + i - 1] = keys[lo + child - 1];
 431                 i = child;
 432             }
 433             keys[lo + i - 1] = d;
 434         }
 435
 436         private static void InsertionSort(T[] keys, int lo, int hi, IComparer<T> comparer)
 437         {
 438             Contract.Requires(keys != null);
 439             Contract.Requires(lo >= 0);
 440             Contract.Requires(hi >= lo);
 441             Contract.Requires(hi <= keys.Length);
 442
 443             int i, j;
 444             T t;
 445             for (i = lo; i < hi; i++)
 446             {
 447                 j = i;
 448                 t = keys[i + 1];
 449                 while (j >= lo && comparer.Compare(t, keys[j]) < 0)
 450                 {
 451                     keys[j + 1] = keys[j];
 452                     j--;
 453                 }
 454                 keys[j + 1] = t;
 455             }
 456         }
 457     }
 458
 459     [Serializable()]
 460     internal class GenericArraySortHelper<T>
 461         : IArraySortHelper<T>
 462         where T : IComparable<T>
 463     {
 464         // Do not add a constructor to this class because ArraySortHelper<T>.CreateSortHelper will not execute it
 465
 466         #region IArraySortHelper<T> Members
 467
 468         public void Sort(T[] keys, int index, int length, IComparer<T> comparer)
 469         {
 470             Contract.Assert(keys != null, "Check the arguments in the caller!");
 471             Contract.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
 472
 473             try
 474             {
 475 #if FEATURE_LEGACYNETCF
 476                 // Pre-Apollo Windows Phone call the overload that sorts the keys, not values this achieves the same result
 477                 if (comparer == null && CompatibilitySwitches.IsAppEarlierThanWindowsPhone8)
 478                     comparer = Comparer<T>.Default;
 479
 480                 if (comparer == null || (comparer == Comparer<T>.Default && !CompatibilitySwitches.IsAppEarlierThanWindowsPhone8)) {
 481 #else
 482                 if (comparer == null || comparer == Comparer<T>.Default) {
 483 #endif
 484
 485 #if FEATURE_CORECLR
 486                     // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade
 487                     // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka
 488                     // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
 489
 490                     IntrospectiveSort(keys, index, length);
 491 #else
 492                     // call the faster version of our sort algorithm if the user doesn't provide a comparer
 493                     if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
 494                     {
 495                         IntrospectiveSort(keys, index, length);
 496                     }
 497                     else
 498                     {
 499                         DepthLimitedQuickSort(keys, index, length + index - 1, IntrospectiveSortUtilities.QuickSortDepthThreshold);
 500                     }
 501 #endif
 502                 }
 503                 else
 504                 {
 505 #if FEATURE_CORECLR
 506                     // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade
 507                     // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka
 508                     // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
 509
 510                     ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer);
 511 #else
 512                     if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
 513                     {
 514                         ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer);
 515                     }
 516                     else
 517                     {
 518                         ArraySortHelper<T>.DepthLimitedQuickSort(keys, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold);
 519                     }
 520 #endif
 521                 }
 522             }
 523             catch (IndexOutOfRangeException)
 524             {
 525                 IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
 526             }
 527             catch (Exception e)
 528             {
 529                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
 530             }
 531         }
 532
 533         public int BinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
 534         {
 535             Contract.Assert(array != null, "Check the arguments in the caller!");
 536             Contract.Assert(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!");
 537
 538             try
 539             {
 540                 if (comparer == null || comparer == Comparer<T>.Default)
 541                 {
 542                     return BinarySearch(array, index, length, value);
 543                 }
 544                 else
 545                 {
 546                     return ArraySortHelper<T>.InternalBinarySearch(array, index, length, value, comparer);
 547                 }
 548             }
 549             catch (Exception e)
 550             {
 551                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
 552             }
 553         }
 554
 555         #endregion
 556
 557         // This function is called when the user doesn't specify any comparer.
 558         // Since T is constrained here, we can call IComparable<T>.CompareTo here.
 559         // We can avoid boxing for value type and casting for reference types.
 560         private static int BinarySearch(T[] array, int index, int length, T value)
 561         {
 562             int lo = index;
 563             int hi = index + length - 1;
 564             while (lo <= hi)
 565             {
 566                 int i = lo + ((hi - lo) >> 1);
 567                 int order;
 568                 if (array[i] == null)
 569                 {
 570                     order = (value == null) ? 0 : -1;
 571                 }
 572                 else
 573                 {
 574                     order = array[i].CompareTo(value);
 575                 }
 576
 577                 if (order == 0)
 578                 {
 579                     return i;
 580                 }
 581
 582                 if (order < 0)
 583                 {
 584                     lo = i + 1;
 585                 }
 586                 else
 587                 {
 588                     hi = i - 1;
 589                 }
 590             }
 591
 592             return ~lo;
 593         }
 594
 595         private static void SwapIfGreaterWithItems(T[] keys, int a, int b)
 596         {
 597             Contract.Requires(keys != null);
 598             Contract.Requires(0 <= a && a < keys.Length);
 599             Contract.Requires(0 <= b && b < keys.Length);
 600
 601             if (a != b)
 602             {
 603                 if (keys[a] != null && keys[a].CompareTo(keys[b]) > 0)
 604                 {
 605                     T key = keys[a];
 606                     keys[a] = keys[b];
 607                     keys[b] = key;
 608                 }
 609             }
 610         }
 611
 612         private static void Swap(T[] a, int i, int j)
 613         {
 614             if(i!=j)
 615             {
 616                 T t = a[i];
 617                 a[i] = a[j];
 618                 a[j] = t;
 619             }
 620         }
 621
 622         private static void DepthLimitedQuickSort(T[] keys, int left, int right, int depthLimit)
 623         {
 624             Contract.Requires(keys != null);
 625             Contract.Requires(0 <= left && left < keys.Length);
 626             Contract.Requires(0 <= right && right < keys.Length);
 627
 628             // The code in this function looks very similar to QuickSort in ArraySortHelper<T> class.
 629             // The difference is that T is constrainted to IComparable<T> here.
 630             // So the IL code will be different. This function is faster than the one in ArraySortHelper<T>.
 631
 632             do
 633             {
 634                 if (depthLimit == 0)
 635                 {
 636                     Heapsort(keys, left, right);
 637                     return;
 638                 }
 639
 640                 int i = left;
 641                 int j = right;
 642
 643                 // pre-sort the low, middle (pivot), and high values in place.
 644                 // this improves performance in the face of already sorted data, or
 645                 // data that is made up of multiple sorted runs appended together.
 646                 int middle = i + ((j - i) >> 1);
 647                 SwapIfGreaterWithItems(keys, i, middle); // swap the low with the mid point
 648                 SwapIfGreaterWithItems(keys, i, j);      // swap the low with the high
 649                 SwapIfGreaterWithItems(keys, middle, j); // swap the middle with the high
 650
 651                 T x = keys[middle];
 652                 do
 653                 {
 654                     if (x == null)
 655                     {
 656                         // if x null, the loop to find two elements to be switched can be reduced.
 657                         while (keys[j] != null) j--;
 658                     }
 659                     else
 660                     {
 661                         while (x.CompareTo(keys[i]) > 0) i++;
 662                         while (x.CompareTo(keys[j]) < 0) j--;
 663                     }
 664                     Contract.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?");
 665                     if (i > j) break;
 666                     if (i < j)
 667                     {
 668                         T key = keys[i];
 669                         keys[i] = keys[j];
 670                         keys[j] = key;
 671                     }
 672                     i++;
 673                     j--;
 674                 } while (i <= j);
 675
 676                 // The next iteration of the while loop is to "recursively" sort the larger half of the array and the
 677                 // following calls recrusively sort the smaller half.  So we subtrack one from depthLimit here so
 678                 // both sorts see the new value.
 679                 depthLimit--;
 680
 681                 if (j - left <= right - i)
 682                 {
 683                     if (left < j) DepthLimitedQuickSort(keys, left, j, depthLimit);
 684                     left = i;
 685                 }
 686                 else
 687                 {
 688                     if (i < right) DepthLimitedQuickSort(keys, i, right, depthLimit);
 689                     right = j;
 690                 }
 691             } while (left < right);
 692         }
 693
 694         internal static void IntrospectiveSort(T[] keys, int left, int length)
 695         {
 696             Contract.Requires(keys != null);
 697             Contract.Requires(left >= 0);
 698             Contract.Requires(length >= 0);
 699             Contract.Requires(length <= keys.Length);
 700             Contract.Requires(length + left <= keys.Length);
 701
 702             if (length < 2)
 703                 return;
 704
 705             IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));
 706         }
 707
 708         private static void IntroSort(T[] keys, int lo, int hi, int depthLimit)
 709         {
 710             Contract.Requires(keys != null);
 711             Contract.Requires(lo >= 0);
 712             Contract.Requires(hi < keys.Length);
 713
 714             while (hi > lo)
 715             {
 716                 int partitionSize = hi - lo + 1;
 717                 if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
 718                 {
 719                     if (partitionSize == 1)
 720                     {
 721                         return;
 722                     }
 723                     if (partitionSize == 2)
 724                     {
 725                         SwapIfGreaterWithItems(keys, lo, hi);
 726                         return;
 727                     }
 728                     if (partitionSize == 3)
 729                     {
 730                         SwapIfGreaterWithItems(keys, lo, hi-1);
 731                         SwapIfGreaterWithItems(keys, lo, hi);
 732                         SwapIfGreaterWithItems(keys, hi-1, hi);
 733                         return;
 734                     }
 735
 736                     InsertionSort(keys, lo, hi);
 737                     return;
 738                 }
 739
 740                 if (depthLimit == 0)
 741                 {
 742                     Heapsort(keys, lo, hi);
 743                     return;
 744                 }
 745                 depthLimit--;
 746
 747                 int p = PickPivotAndPartition(keys, lo, hi);
 748                 // Note we've already partitioned around the pivot and do not have to move the pivot again.
 749                 IntroSort(keys, p + 1, hi, depthLimit);
 750                 hi = p - 1;
 751             }
 752         }
 753
 754         private static int PickPivotAndPartition(T[] keys, int lo, int hi)
 755         {
 756             Contract.Requires(keys != null);
 757             Contract.Requires(lo >= 0);
 758             Contract.Requires(hi > lo);
 759             Contract.Requires(hi < keys.Length);
 760             Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi);
 761
 762             // Compute median-of-three.  But also partition them, since we've done the comparison.
 763             int middle = lo + ((hi - lo) / 2);
 764
 765             // Sort lo, mid and hi appropriately, then pick mid as the pivot.
 766             SwapIfGreaterWithItems(keys, lo, middle);  // swap the low with the mid point
 767             SwapIfGreaterWithItems(keys, lo, hi);   // swap the low with the high
 768             SwapIfGreaterWithItems(keys, middle, hi); // swap the middle with the high
 769
 770             T pivot = keys[middle];
 771             Swap(keys, middle, hi - 1);
 772             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.
 773
 774             while (left < right)
 775             {
 776                 if (pivot == null)
 777                 {
 778                     while (left < (hi - 1) && keys[++left] == null) ;
 779                     while (right > lo && keys[--right] != null) ;
 780                 }
 781                 else
 782                 {
 783                     while (pivot.CompareTo(keys[++left]) > 0) ;
 784                     while (pivot.CompareTo(keys[--right]) < 0) ;
 785                 }
 786
 787                 if (left >= right)
 788                     break;
 789
 790                 Swap(keys, left, right);
 791             }
 792
 793             // Put pivot in the right location.
 794             Swap(keys, left, (hi - 1));
 795             return left;
 796         }
 797
 798         private static void Heapsort(T[] keys, int lo, int hi)
 799         {
 800             Contract.Requires(keys != null);
 801             Contract.Requires(lo >= 0);
 802             Contract.Requires(hi > lo);
 803             Contract.Requires(hi < keys.Length);
 804
 805             int n = hi - lo + 1;
 806             for (int i = n / 2; i >= 1; i = i - 1)
 807             {
 808                 DownHeap(keys, i, n, lo);
 809             }
 810             for (int i = n; i > 1; i = i - 1)
 811             {
 812                 Swap(keys, lo, lo + i - 1);
 813                 DownHeap(keys, 1, i - 1, lo);
 814             }
 815         }
 816
 817         private static void DownHeap(T[] keys, int i, int n, int lo)
 818         {
 819             Contract.Requires(keys != null);
 820             Contract.Requires(lo >= 0);
 821             Contract.Requires(lo < keys.Length);
 822
 823             T d = keys[lo + i - 1];
 824             int child;
 825             while (i <= n / 2)
 826             {
 827                 child = 2 * i;
 828                 if (child < n && (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(keys[lo + child]) < 0))
 829                 {
 830                     child++;
 831                 }
 832                 if (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(d) < 0)
 833                     break;
 834                 keys[lo + i - 1] = keys[lo + child - 1];
 835                 i = child;
 836             }
 837             keys[lo + i - 1] = d;
 838         }
 839
 840         private static void InsertionSort(T[] keys, int lo, int hi)
 841         {
 842             Contract.Requires(keys != null);
 843             Contract.Requires(lo >= 0);
 844             Contract.Requires(hi >= lo);
 845             Contract.Requires(hi <= keys.Length);
 846
 847             int i, j;
 848             T t;
 849             for (i = lo; i < hi; i++)
 850             {
 851                 j = i;
 852                 t = keys[i + 1];
 853                 while (j >= lo && (t == null || t.CompareTo(keys[j]) < 0))
 854                 {
 855                     keys[j + 1] = keys[j];
 856                     j--;
 857                 }
 858                 keys[j + 1] = t;
 859             }
 860         }
 861     }
 862
 863     #endregion
 864
 865     #region ArraySortHelper for paired key and value arrays
 866
 867     internal interface IArraySortHelper<TKey, TValue>
 868     {
 869         void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer);
 870     }
 871
 872     [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`2")]
 873     internal class ArraySortHelper<TKey, TValue>
 874         : IArraySortHelper<TKey, TValue>
 875     {
 876         static volatile IArraySortHelper<TKey, TValue> defaultArraySortHelper;
 877
 878         public static IArraySortHelper<TKey, TValue> Default
 879         {
 880             get
 881             {
 882                 IArraySortHelper<TKey, TValue> sorter = defaultArraySortHelper;
 883                 if (sorter == null)
 884                     sorter = CreateArraySortHelper();
 885
 886                 return sorter;
 887             }
 888         }
 889
 890         [System.Security.SecuritySafeCritical]  // auto-generated
 891         private static IArraySortHelper<TKey, TValue> CreateArraySortHelper()
 892         {
 893             if (typeof(IComparable<TKey>).IsAssignableFrom(typeof(TKey)))
 894             {
 895                 defaultArraySortHelper = (IArraySortHelper<TKey, TValue>)RuntimeTypeHandle.Allocate(typeof(GenericArraySortHelper<string, string>).TypeHandle.Instantiate(new Type[] { typeof(TKey), typeof(TValue) }));
 896             }
 897             else
 898             {
 899                 defaultArraySortHelper = new ArraySortHelper<TKey, TValue>();
 900             }
 901             return defaultArraySortHelper;
 902         }
 903
 904         public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer)
 905         {
 906             Contract.Assert(keys != null, "Check the arguments in the caller!");  // Precondition on interface method
 907             Contract.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
 908
 909             // Add a try block here to detect IComparers (or their
 910             // underlying IComparables, etc) that are bogus.
 911             try
 912             {
 913                 if (comparer == null || comparer == Comparer<TKey>.Default)
 914                 {
 915                     comparer = Comparer<TKey>.Default;
 916                 }
 917
 918 #if FEATURE_CORECLR
 919                 // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade
 920                 // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka
 921                 // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
 922
 923                 IntrospectiveSort(keys, values, index, length, comparer);
 924 #else
 925                 if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
 926                 {
 927                     IntrospectiveSort(keys, values, index, length, comparer);
 928                 }
 929                 else
 930                 {
 931                     DepthLimitedQuickSort(keys, values, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold);
 932                 }
 933 #endif
 934             }
 935             catch (IndexOutOfRangeException)
 936             {
 937                 IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
 938             }
 939             catch (Exception e)
 940             {
 941                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
 942             }
 943         }
 944
 945         private static void SwapIfGreaterWithItems(TKey[] keys, TValue[] values, IComparer<TKey> comparer, int a, int b)
 946         {
 947             Contract.Requires(keys != null);
 948             Contract.Requires(values == null || values.Length >= keys.Length);
 949             Contract.Requires(comparer != null);
 950             Contract.Requires(0 <= a && a < keys.Length);
 951             Contract.Requires(0 <= b && b < keys.Length);
 952
 953             if (a != b)
 954             {
 955                 if (comparer.Compare(keys[a], keys[b]) > 0)
 956                 {
 957                     TKey key = keys[a];
 958                     keys[a] = keys[b];
 959                     keys[b] = key;
 960                     if (values != null)
 961                     {
 962                         TValue value = values[a];
 963                         values[a] = values[b];
 964                         values[b] = value;
 965                     }
 966                 }
 967             }
 968         }
 969
 970         private static void Swap(TKey[] keys, TValue[] values, int i, int j)
 971         {
 972             if(i!=j)
 973             {
 974                 TKey k = keys[i];
 975                 keys[i] = keys[j];
 976                 keys[j] = k;
 977                 if(values != null)
 978                 {
 979                     TValue v = values[i];
 980                     values[i] = values[j];
 981                     values[j] = v;
 982                 }
 983             }
 984         }
 985
 986         internal static void DepthLimitedQuickSort(TKey[] keys, TValue[] values, int left, int right, IComparer<TKey> comparer, int depthLimit)
 987         {
 988             do
 989             {
 990                 if (depthLimit == 0)
 991                 {
 992                     Heapsort(keys, values, left, right, comparer);
 993                     return;
 994                 }
 995
 996                 int i = left;
 997                 int j = right;
 998
 999                 // pre-sort the low, middle (pivot), and high values in place.
1000                 // this improves performance in the face of already sorted data, or
1001                 // data that is made up of multiple sorted runs appended together.
1002                 int middle = i + ((j - i) >> 1);
1003                 SwapIfGreaterWithItems(keys, values, comparer, i, middle);  // swap the low with the mid point
1004                 SwapIfGreaterWithItems(keys, values, comparer, i, j);   // swap the low with the high
1005                 SwapIfGreaterWithItems(keys, values, comparer, middle, j); // swap the middle with the high
1006
1007                 TKey x = keys[middle];
1008                 do
1009                 {
1010                     while (comparer.Compare(keys[i], x) < 0) i++;
1011                     while (comparer.Compare(x, keys[j]) < 0) j--;
1012                     Contract.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?");
1013                     if (i > j) break;
1014                     if (i < j)
1015                     {
1016                         TKey key = keys[i];
1017                         keys[i] = keys[j];
1018                         keys[j] = key;
1019                         if (values != null)
1020                         {
1021                             TValue value = values[i];
1022                             values[i] = values[j];
1023                             values[j] = value;
1024                         }
1025                     }
1026                     i++;
1027                     j--;
1028                 } while (i <= j);
1029
1030                 // The next iteration of the while loop is to "recursively" sort the larger half of the array and the
1031                 // following calls recrusively sort the smaller half.  So we subtrack one from depthLimit here so
1032                 // both sorts see the new value.
1033                 depthLimit--;
1034
1035                 if (j - left <= right - i)
1036                 {
1037                     if (left < j) DepthLimitedQuickSort(keys, values, left, j, comparer, depthLimit);
1038                     left = i;
1039                 }
1040                 else
1041                 {
1042                     if (i < right) DepthLimitedQuickSort(keys, values, i, right, comparer, depthLimit);
1043                     right = j;
1044                 }
1045             } while (left < right);
1046         }
1047
1048         internal static void IntrospectiveSort(TKey[] keys, TValue[] values, int left, int length, IComparer<TKey> comparer)
1049         {
1050             Contract.Requires(keys != null);
1051             Contract.Requires(values != null);
1052             Contract.Requires(comparer != null);
1053             Contract.Requires(left >= 0);
1054             Contract.Requires(length >= 0);
1055             Contract.Requires(length <= keys.Length);
1056             Contract.Requires(length + left <= keys.Length);
1057             Contract.Requires(length + left <= values.Length);
1058
1059             if (length < 2)
1060                 return;
1061
1062             IntroSort(keys, values, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer);
1063         }
1064
1065         private static void IntroSort(TKey[] keys, TValue[] values, int lo, int hi, int depthLimit, IComparer<TKey> comparer)
1066         {
1067             Contract.Requires(keys != null);
1068             Contract.Requires(values != null);
1069             Contract.Requires(comparer != null);
1070             Contract.Requires(lo >= 0);
1071             Contract.Requires(hi < keys.Length);
1072
1073             while (hi > lo)
1074             {
1075                 int partitionSize = hi - lo + 1;
1076                 if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
1077                 {
1078                     if (partitionSize == 1)
1079                     {
1080                         return;
1081                     }
1082                     if (partitionSize == 2)
1083                     {
1084                         SwapIfGreaterWithItems(keys, values, comparer, lo, hi);
1085                         return;
1086                     }
1087                     if (partitionSize == 3)
1088                     {
1089                         SwapIfGreaterWithItems(keys, values, comparer, lo, hi-1);
1090                         SwapIfGreaterWithItems(keys, values, comparer, lo, hi);
1091                         SwapIfGreaterWithItems(keys, values, comparer, hi-1, hi);
1092                         return;
1093                     }
1094
1095                     InsertionSort(keys, values, lo, hi, comparer);
1096                     return;
1097                 }
1098
1099                 if (depthLimit == 0)
1100                 {
1101                     Heapsort(keys, values, lo, hi, comparer);
1102                     return;
1103                 }
1104                 depthLimit--;
1105
1106                 int p = PickPivotAndPartition(keys, values, lo, hi, comparer);
1107                 // Note we've already partitioned around the pivot and do not have to move the pivot again.
1108                 IntroSort(keys, values, p + 1, hi, depthLimit, comparer);
1109                 hi = p - 1;
1110             }
1111         }
1112
1113         private static int PickPivotAndPartition(TKey[] keys, TValue[] values, int lo, int hi, IComparer<TKey> comparer)
1114         {
1115             Contract.Requires(keys != null);
1116             Contract.Requires(values != null);
1117             Contract.Requires(comparer != null);
1118             Contract.Requires(lo >= 0);
1119             Contract.Requires(hi > lo);
1120             Contract.Requires(hi < keys.Length);
1121             Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi);
1122
1123             // Compute median-of-three.  But also partition them, since we've done the comparison.
1124             int middle = lo + ((hi - lo) / 2);
1125
1126             // Sort lo, mid and hi appropriately, then pick mid as the pivot.
1127             SwapIfGreaterWithItems(keys, values, comparer, lo, middle);  // swap the low with the mid point
1128             SwapIfGreaterWithItems(keys, values, comparer, lo, hi);   // swap the low with the high
1129             SwapIfGreaterWithItems(keys, values, comparer, middle, hi); // swap the middle with the high
1130
1131             TKey pivot = keys[middle];
1132             Swap(keys, values, middle, hi - 1);
1133             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.
1134
1135             while (left < right)
1136             {
1137                 while (comparer.Compare(keys[++left], pivot) < 0) ;
1138                 while (comparer.Compare(pivot, keys[--right]) < 0) ;
1139
1140                 if (left >= right)
1141                     break;
1142
1143                 Swap(keys, values, left, right);
1144             }
1145
1146             // Put pivot in the right location.
1147             Swap(keys, values, left, (hi - 1));
1148             return left;
1149         }
1150
1151         private static void Heapsort(TKey[] keys, TValue[] values, int lo, int hi, IComparer<TKey> comparer)
1152         {
1153             Contract.Requires(keys != null);
1154             Contract.Requires(values != null);
1155             Contract.Requires(comparer != null);
1156             Contract.Requires(lo >= 0);
1157             Contract.Requires(hi > lo);
1158             Contract.Requires(hi < keys.Length);
1159
1160             int n = hi - lo + 1;
1161             for (int i = n / 2; i >= 1; i = i - 1)
1162             {
1163                 DownHeap(keys, values, i, n, lo, comparer);
1164             }
1165             for (int i = n; i > 1; i = i - 1)
1166             {
1167                 Swap(keys, values, lo, lo + i - 1);
1168                 DownHeap(keys, values, 1, i - 1, lo, comparer);
1169             }
1170         }
1171
1172         private static void DownHeap(TKey[] keys, TValue[] values, int i, int n, int lo, IComparer<TKey> comparer)
1173         {
1174             Contract.Requires(keys != null);
1175             Contract.Requires(comparer != null);
1176             Contract.Requires(lo >= 0);
1177             Contract.Requires(lo < keys.Length);
1178
1179             TKey d = keys[lo + i - 1];
1180             TValue dValue = (values != null) ? values[lo + i - 1] : default(TValue);
1181             int child;
1182             while (i <= n / 2)
1183             {
1184                 child = 2 * i;
1185                 if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0)
1186                 {
1187                     child++;
1188                 }
1189                 if (!(comparer.Compare(d, keys[lo + child - 1]) < 0))
1190                     break;
1191                 keys[lo + i - 1] = keys[lo + child - 1];
1192                 if(values != null)
1193                     values[lo + i - 1] = values[lo + child - 1];
1194                 i = child;
1195             }
1196             keys[lo + i - 1] = d;
1197             if(values != null)
1198                 values[lo + i - 1] = dValue;
1199         }
1200
1201         private static void InsertionSort(TKey[] keys, TValue[] values, int lo, int hi, IComparer<TKey> comparer)
1202         {
1203             Contract.Requires(keys != null);
1204             Contract.Requires(values != null);
1205             Contract.Requires(comparer != null);
1206             Contract.Requires(lo >= 0);
1207             Contract.Requires(hi >= lo);
1208             Contract.Requires(hi <= keys.Length);
1209
1210             int i, j;
1211             TKey t;
1212             TValue tValue;
1213             for (i = lo; i < hi; i++)
1214             {
1215                 j = i;
1216                 t = keys[i + 1];
1217                 tValue = (values != null) ? values[i + 1] : default(TValue);
1218                 while (j >= lo && comparer.Compare(t, keys[j]) < 0)
1219                 {
1220                     keys[j + 1] = keys[j];
1221                     if(values != null)
1222                         values[j + 1] = values[j];
1223                     j--;
1224                 }
1225                 keys[j + 1] = t;
1226                 if(values != null)
1227                     values[j + 1] = tValue;
1228             }
1229         }
1230     }
1231
1232     internal class GenericArraySortHelper<TKey, TValue>
1233         : IArraySortHelper<TKey, TValue>
1234         where TKey : IComparable<TKey>
1235     {
1236         public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer)
1237         {
1238             Contract.Assert(keys != null, "Check the arguments in the caller!");
1239             Contract.Assert( index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
1240
1241             // Add a try block here to detect IComparers (or their
1242             // underlying IComparables, etc) that are bogus.
1243             try
1244             {
1245                 if (comparer == null || comparer == Comparer<TKey>.Default)
1246                 {
1247 #if FEATURE_CORECLR
1248                     // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade
1249                     // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka
1250                     // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
1251
1252                     IntrospectiveSort(keys, values, index, length);
1253 #else
1254                     // call the faster version of our sort algorithm if the user doesn't provide a comparer
1255                     if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
1256                     {
1257                         IntrospectiveSort(keys, values, index, length);
1258                     }
1259                     else
1260                     {
1261                         DepthLimitedQuickSort(keys, values, index, length + index - 1, IntrospectiveSortUtilities.QuickSortDepthThreshold);
1262                     }
1263 #endif
1264                 }
1265                 else
1266                 {
1267 #if FEATURE_CORECLR
1268                     // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade
1269                     // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka
1270                     // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
1271
1272                     ArraySortHelper<TKey, TValue>.IntrospectiveSort(keys, values, index, length, comparer);
1273 #else
1274                     if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
1275                     {
1276                         ArraySortHelper<TKey, TValue>.IntrospectiveSort(keys, values, index, length, comparer);
1277                     }
1278                     else
1279                     {
1280                         ArraySortHelper<TKey, TValue>.DepthLimitedQuickSort(keys, values, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold);
1281                     }
1282 #endif
1283                 }
1284
1285             }
1286             catch (IndexOutOfRangeException)
1287             {
1288                 IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
1289             }
1290             catch (Exception e)
1291             {
1292                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
1293             }
1294         }
1295
1296         private static void SwapIfGreaterWithItems(TKey[] keys, TValue[] values, int a, int b)
1297         {
1298             if (a != b)
1299             {
1300                 if (keys[a] != null && keys[a].CompareTo(keys[b]) > 0)
1301                 {
1302                     TKey key = keys[a];
1303                     keys[a] = keys[b];
1304                     keys[b] = key;
1305                     if (values != null)
1306                     {
1307                         TValue value = values[a];
1308                         values[a] = values[b];
1309                         values[b] = value;
1310                     }
1311                 }
1312             }
1313         }
1314
1315         private static void Swap(TKey[] keys, TValue[] values, int i, int j)
1316         {
1317             if(i != j)
1318             {
1319                 TKey k = keys[i];
1320                 keys[i] = keys[j];
1321                 keys[j] = k;
1322                 if(values != null)
1323                 {
1324                     TValue v = values[i];
1325                     values[i] = values[j];
1326                     values[j] = v;
1327                 }
1328             }
1329         }
1330
1331         private static void DepthLimitedQuickSort(TKey[] keys, TValue[] values, int left, int right, int depthLimit)
1332         {
1333             // The code in this function looks very similar to QuickSort in ArraySortHelper<T> class.
1334             // The difference is that T is constrainted to IComparable<T> here.
1335             // So the IL code will be different. This function is faster than the one in ArraySortHelper<T>.
1336
1337             do
1338             {
1339                 if (depthLimit == 0)
1340                 {
1341                     Heapsort(keys, values, left, right);
1342                     return;
1343                 }
1344
1345                 int i = left;
1346                 int j = right;
1347
1348                 // pre-sort the low, middle (pivot), and high values in place.
1349                 // this improves performance in the face of already sorted data, or
1350                 // data that is made up of multiple sorted runs appended together.
1351                 int middle = i + ((j - i) >> 1);
1352                 SwapIfGreaterWithItems(keys, values, i, middle); // swap the low with the mid point
1353                 SwapIfGreaterWithItems(keys, values, i, j);      // swap the low with the high
1354                 SwapIfGreaterWithItems(keys, values, middle, j); // swap the middle with the high
1355
1356                 TKey x = keys[middle];
1357                 do
1358                 {
1359                     if (x == null)
1360                     {
1361                         // if x null, the loop to find two elements to be switched can be reduced.
1362                         while (keys[j] != null) j--;
1363                     }
1364                     else
1365                     {
1366                         while (x.CompareTo(keys[i]) > 0) i++;
1367                         while (x.CompareTo(keys[j]) < 0) j--;
1368                     }
1369                     Contract.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?");
1370                     if (i > j) break;
1371                     if (i < j)
1372                     {
1373                         TKey key = keys[i];
1374                         keys[i] = keys[j];
1375                         keys[j] = key;
1376                         if (values != null)
1377                         {
1378                             TValue value = values[i];
1379                             values[i] = values[j];
1380                             values[j] = value;
1381                         }
1382                     }
1383                     i++;
1384                     j--;
1385                 } while (i <= j);
1386
1387                 // The next iteration of the while loop is to "recursively" sort the larger half of the array and the
1388                 // following calls recrusively sort the smaller half.  So we subtrack one from depthLimit here so
1389                 // both sorts see the new value.
1390                 depthLimit--;
1391
1392                 if (j - left <= right - i)
1393                 {
1394                     if (left < j) DepthLimitedQuickSort(keys, values, left, j, depthLimit);
1395                     left = i;
1396                 }
1397                 else
1398                 {
1399                     if (i < right) DepthLimitedQuickSort(keys, values, i, right, depthLimit);
1400                     right = j;
1401                 }
1402             } while (left < right);
1403         }
1404
1405         internal static void IntrospectiveSort(TKey[] keys, TValue[] values, int left, int length)
1406         {
1407             Contract.Requires(keys != null);
1408             Contract.Requires(values != null);
1409             Contract.Requires(left >= 0);
1410             Contract.Requires(length >= 0);
1411             Contract.Requires(length <= keys.Length);
1412             Contract.Requires(length + left <= keys.Length);
1413             Contract.Requires(length + left <= values.Length);
1414
1415             if (length < 2)
1416                 return;
1417
1418             IntroSort(keys, values, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));
1419         }
1420
1421         private static void IntroSort(TKey[] keys, TValue[] values, int lo, int hi, int depthLimit)
1422         {
1423             Contract.Requires(keys != null);
1424             Contract.Requires(values != null);
1425             Contract.Requires(lo >= 0);
1426             Contract.Requires(hi < keys.Length);
1427
1428             while (hi > lo)
1429             {
1430                 int partitionSize = hi - lo + 1;
1431                 if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
1432                 {
1433                     if (partitionSize == 1)
1434                     {
1435                         return;
1436                     }
1437                     if (partitionSize == 2)
1438                     {
1439                         SwapIfGreaterWithItems(keys, values, lo, hi);
1440                         return;
1441                     }
1442                     if (partitionSize == 3)
1443                     {
1444                         SwapIfGreaterWithItems(keys, values, lo, hi-1);
1445                         SwapIfGreaterWithItems(keys, values, lo, hi);
1446                         SwapIfGreaterWithItems(keys, values, hi-1, hi);
1447                         return;
1448                     }
1449
1450                     InsertionSort(keys, values, lo, hi);
1451                     return;
1452                 }
1453
1454                 if (depthLimit == 0)
1455                 {
1456                     Heapsort(keys, values, lo, hi);
1457                     return;
1458                 }
1459                 depthLimit--;
1460
1461                 int p = PickPivotAndPartition(keys, values, lo, hi);
1462                 // Note we've already partitioned around the pivot and do not have to move the pivot again.
1463                 IntroSort(keys, values, p + 1, hi, depthLimit);
1464                 hi = p - 1;
1465             }
1466         }
1467
1468         private static int PickPivotAndPartition(TKey[] keys, TValue[] values, int lo, int hi)
1469         {
1470             Contract.Requires(keys != null);
1471             Contract.Requires(values != null);
1472             Contract.Requires(lo >= 0);
1473             Contract.Requires(hi > lo);
1474             Contract.Requires(hi < keys.Length);
1475             Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi);
1476
1477             // Compute median-of-three.  But also partition them, since we've done the comparison.
1478             int middle = lo + ((hi - lo) / 2);
1479
1480             // Sort lo, mid and hi appropriately, then pick mid as the pivot.
1481             SwapIfGreaterWithItems(keys, values, lo, middle);  // swap the low with the mid point
1482             SwapIfGreaterWithItems(keys, values, lo, hi);   // swap the low with the high
1483             SwapIfGreaterWithItems(keys, values, middle, hi); // swap the middle with the high
1484
1485             TKey pivot = keys[middle];
1486             Swap(keys, values, middle, hi - 1);
1487             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.
1488
1489             while (left < right)
1490             {
1491                 if(pivot == null)
1492                 {
1493                     while (left < (hi - 1) && keys[++left] == null) ;
1494                     while (right > lo && keys[--right] != null);
1495                 }
1496                 else
1497                 {
1498                     while (pivot.CompareTo(keys[++left]) > 0) ;
1499                     while (pivot.CompareTo(keys[--right]) < 0) ;
1500                 }
1501
1502                 if (left >= right)
1503                     break;
1504
1505                 Swap(keys, values, left, right);
1506             }
1507
1508             // Put pivot in the right location.
1509             Swap(keys, values, left, (hi - 1));
1510             return left;
1511         }
1512
1513         private static void Heapsort(TKey[] keys, TValue[] values, int lo, int hi)
1514         {
1515             Contract.Requires(keys != null);
1516             Contract.Requires(values != null);
1517             Contract.Requires(lo >= 0);
1518             Contract.Requires(hi > lo);
1519             Contract.Requires(hi < keys.Length);
1520
1521             int n = hi - lo + 1;
1522             for (int i = n / 2; i >= 1; i = i - 1)
1523             {
1524                 DownHeap(keys, values, i, n, lo);
1525             }
1526             for (int i = n; i > 1; i = i - 1)
1527             {
1528                 Swap(keys, values, lo, lo + i - 1);
1529                 DownHeap(keys, values, 1, i - 1, lo);
1530             }
1531         }
1532
1533         private static void DownHeap(TKey[] keys, TValue[] values, int i, int n, int lo)
1534         {
1535             Contract.Requires(keys != null);
1536             Contract.Requires(lo >= 0);
1537             Contract.Requires(lo < keys.Length);
1538
1539             TKey d = keys[lo + i - 1];
1540             TValue dValue = (values != null) ? values[lo + i - 1] : default(TValue);
1541             int child;
1542             while (i <= n / 2)
1543             {
1544                 child = 2 * i;
1545                 if (child < n && (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(keys[lo + child]) < 0))
1546                 {
1547                     child++;
1548                 }
1549                 if (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(d) < 0)
1550                     break;
1551                 keys[lo + i - 1] = keys[lo + child - 1];
1552                 if(values != null)
1553                     values[lo + i - 1] = values[lo + child - 1];
1554                 i = child;
1555             }
1556             keys[lo + i - 1] = d;
1557             if(values != null)
1558                 values[lo + i - 1] = dValue;
1559         }
1560
1561         private static void InsertionSort(TKey[] keys, TValue[] values, int lo, int hi)
1562         {
1563             Contract.Requires(keys != null);
1564             Contract.Requires(values != null);
1565             Contract.Requires(lo >= 0);
1566             Contract.Requires(hi >= lo);
1567             Contract.Requires(hi <= keys.Length);
1568
1569             int i, j;
1570             TKey t;
1571             TValue tValue;
1572             for (i = lo; i < hi; i++)
1573             {
1574                 j = i;
1575                 t = keys[i + 1];
1576                 tValue = (values != null)? values[i + 1] : default(TValue);
1577                 while (j >= lo && (t == null || t.CompareTo(keys[j]) < 0))
1578                 {
1579                     keys[j + 1] = keys[j];
1580                     if(values != null)
1581                         values[j + 1] = values[j];
1582                     j--;
1583                 }
1584                 keys[j + 1] = t;
1585                 if(values != null)
1586                     values[j + 1] = tValue;
1587             }
1588         }
1589     }
1590
1591     #endregion
1592 }
1593
1594