1 struct QSortStack {2             public int high;3             public int low;4         }

1     QSortStack* stack = stackalloc QSortStack [32];

1     unsafe static void qsort
     
       (T[] keys, U[] items, int low0, int high0) where T : IComparable
      
         2         {  3             QSortStack* stack = stackalloc QSortStack [32];  4             const int QSORT_THRESHOLD = 7;  5             int high, low, mid, i, k;  6             int sp = 1;  7             T key;  8               9             // initialize our stack 10             stack[0].high = high0; 11             stack[0].low = low0; 12              13             do { 14                 // pop the stack 15                 sp--; 16                 high = stack[sp].high; 17                 low = stack[sp].low; 18                  19                 if ((low + QSORT_THRESHOLD) > high) { 20                     // switch to insertion sort 21                     for (i = low + 1; i <= high; i++) { 22                         for (k = i; k > low; k--) { 23                             // if keys[k] >= keys[k-1], break 24                             if (keys[k-1] == null) 25                                 break; 26                              27                             if (keys[k] != null && keys[k].CompareTo (keys[k-1]) >= 0) 28                                 break; 29                              30                             swap (keys, items, k - 1, k); 31                         } 32                     } 33                      34                     continue; 35                 } 36                  37                 // calculate the middle element 38                 mid = low + ((high - low) / 2); 39                  40                 // once we re-order the lo, mid, and hi elements to be in 41                 // ascending order, we'll use mid as our pivot. 42                 QSortArrange
       
         (keys, items, low, mid); 43                 if (QSortArrange
        
          (keys, items, mid, high)) 44                     QSortArrange
         
           (keys, items, low, mid); 45                  46                 key = keys[mid]; 47                  48                 // since we've already guaranteed that lo <= mid and mid <= hi, 49                 // we can skip comparing them again 50                 k = high - 1; 51                 i = low + 1; 52                  53                 do { 54                     if (key != null) { 55                         // find the first element with a value >= pivot value 56                         while (i < k && key.CompareTo (keys[i]) > 0) 57                             i++; 58                          59                         // find the last element with a value <= pivot value 60                         while (k > i && key.CompareTo (keys[k]) < 0) 61                             k--; 62                     } else { 63                         while (i < k && keys[i] == null) 64                             i++; 65                          66                         while (k > i && keys[k] != null) 67                             k--; 68                     } 69                      70                     if (k <= i) 71                         break; 72                      73                     swap (keys, items, i, k); 74                      75                     i++; 76                     k--; 77                 } while (true); 78                  79                 // push our partitions onto the stack, largest first 80                 // (to make sure we don't run out of stack space) 81                 if ((high - k) >= (k - low)) { 82                     if ((k + 1) < high) { 83                         stack[sp].high = high; 84                         stack[sp].low = k; 85                         sp++; 86                     } 87                      88                     if ((k - 1) > low) { 89                         stack[sp].high = k; 90                         stack[sp].low = low; 91                         sp++; 92                     } 93                 } else { 94                     if ((k - 1) > low) { 95                         stack[sp].high = k; 96                         stack[sp].low = low; 97                         sp++; 98                     } 99                     100                     if ((k + 1) < high) {101                         stack[sp].high = high;102                         stack[sp].low = k;103                         sp++;104                     }105                 }106             } while (sp > 0);107         }        108 109         // Specialized version for items==null110         unsafe static void qsort
          
            (T[] keys, int low0, int high0) where T : IComparable
           
            111 {112 QSortStack* stack = stackalloc QSortStack [32];113 const int QSORT_THRESHOLD = 7;114 int high, low, mid, i, k;115 int sp = 1;116 T key;117 118 // initialize our stack119 stack[0].high = high0;120 stack[0].low = low0;121 122 do {123 // pop the stack124 sp--;125 high = stack[sp].high;126 low = stack[sp].low;127 128 if ((low + QSORT_THRESHOLD) > high) {129 // switch to insertion sort130 for (i = low + 1; i <= high; i++) {131 for (k = i; k > low; k--) {132 // if keys[k] >= keys[k-1], break133 if (keys[k-1] == null)134 break;135 136 if (keys[k] != null && keys[k].CompareTo (keys[k-1]) >= 0)137 break;138 139 swap (keys, k - 1, k);140 }141 }142 143 continue;144 }145 146 // calculate the middle element147 mid = low + ((high - low) / 2);148 149 // once we re-order the lo, mid, and hi elements to be in150 // ascending order, we'll use mid as our pivot.151 QSortArrange
            
              (keys, low, mid);152 if (QSortArrange
             
               (keys, mid, high))153 QSortArrange
              
                (keys, low, mid);154 155 key = keys[mid];156 157 // since we've already guaranteed that lo <= mid and mid <= hi,158 // we can skip comparing them again159 k = high - 1;160 i = low + 1;161 162 do {163 if (key != null) {164 // find the first element with a value >= pivot value165 while (i < k && key.CompareTo (keys[i]) > 0)166 i++;167 168 // find the last element with a value <= pivot value169 while (k >= i && key.CompareTo (keys[k]) < 0)170 k--;171 } else {172 while (i < k && keys[i] == null)173 i++;174 175 while (k >= i && keys[k] != null)176 k--;177 }178 179 if (k <= i)180 break;181 182 swap (keys, i, k);183 184 i++;185 k--;186 } while (true);187 188 // push our partitions onto the stack, largest first189 // (to make sure we don't run out of stack space)190 if ((high - k) >= (k - low)) {191 if ((k + 1) < high) {192 stack[sp].high = high;193 stack[sp].low = k;194 sp++;195 }196 197 if ((k - 1) > low) {198 stack[sp].high = k;199 stack[sp].low = low;200 sp++;201 }202 } else {203 if ((k - 1) > low) {204 stack[sp].high = k;205 stack[sp].low = low;206 sp++;207 }208 209 if ((k + 1) < high) {210 stack[sp].high = high;211 stack[sp].low = k;212 sp++;213 }214 }215 } while (sp > 0);216 }217 218 static bool QSortArrange
               
                 (K [] keys, V [] items, int lo, int hi, IComparer
                
                  comparer)219 {220 IComparable
                 
                   gcmp;221 IComparable cmp;222 223 if (comparer != null) {224 if (comparer.Compare (keys[hi], keys[lo]) < 0) {225 swap
                  
                    (keys, items, lo, hi);226 return true;227 }228 } else if (keys[lo] != null) {229 if (keys[hi] == null) {230 swap
                   
                     (keys, items, lo, hi);231 return true;232 }233 234 gcmp = keys[hi] as IComparable
                    
                     ;235 if (gcmp != null) {236 if (gcmp.CompareTo (keys[lo]) < 0) {237 swap
                     
                       (keys, items, lo, hi);238 return true;239 }240 241 return false;242 }243 244 cmp = keys[hi] as IComparable;245 if (cmp != null) {246 if (cmp.CompareTo (keys[lo]) < 0) {247 swap
                      
                        (keys, items, lo, hi);248 return true;249 }250 251 return false;252 }253 }254 255 return false;256 }257 258 // Specialized version for items==null259 static bool QSortArrange
                       
                         (K [] keys, int lo, int hi, IComparer
                        
                          comparer)260 {261 IComparable
                         
                           gcmp;262 IComparable cmp;263 264 if (comparer != null) {265 if (comparer.Compare (keys[hi], keys[lo]) < 0) {266 swap
                          
                            (keys, lo, hi);267 return true;268 }269 } else if (keys[lo] != null) {270 if (keys[hi] == null) {271 swap
                           
                             (keys, lo, hi);272 return true;273 }274 275 gcmp = keys[hi] as IComparable
                            
                             ;276 if (gcmp != null) {277 if (gcmp.CompareTo (keys[lo]) < 0) {278 swap
                             
                               (keys, lo, hi);279 return true;280 }281 282 return false;283 }284 285 cmp = keys[hi] as IComparable;286 if (cmp != null) {287 if (cmp.CompareTo (keys[lo]) < 0) {288 swap
                              
                                (keys, lo, hi);289 return true;290 }291 292 return false;293 }294 }295 296 return false;297 }298 299 unsafe static void qsort
                               
                                 (K [] keys, V [] items, int low0, int high0, IComparer
                                
                                  comparer)300 {301 QSortStack* stack = stackalloc QSortStack [32];302 const int QSORT_THRESHOLD = 7;303 int high, low, mid, i, k;304 IComparable
                                 
                                   gcmp;305 IComparable cmp;306 int sp = 1;307 K key;308 309 // initialize our stack310 stack[0].high = high0;311 stack[0].low = low0;312 313 do {314 // pop the stack315 sp--;316 high = stack[sp].high;317 low = stack[sp].low;318 319 if ((low + QSORT_THRESHOLD) > high) {320 // switch to insertion sort321 for (i = low + 1; i <= high; i++) {322 for (k = i; k > low; k--) {323 // if keys[k] >= keys[k-1], break324 if (comparer != null) {325 if (comparer.Compare (keys[k], keys[k-1]) >= 0)326 break;327 } else {328 if (keys[k-1] == null)329 break;330 331 if (keys[k] != null) {332 gcmp = keys[k] as IComparable
                                  
                                   ;333 cmp = keys[k] as IComparable;334 if (gcmp != null) {335 if (gcmp.CompareTo (keys[k-1]) >= 0)336 break;337 } else {338 if (cmp.CompareTo (keys[k-1]) >= 0)339 break;340 }341 }342 }343 344 swap
                                   
                                     (keys, items, k - 1, k);345 }346 }347 348 continue;349 }350 351 // calculate the middle element352 mid = low + ((high - low) / 2);353 354 // once we re-order the low, mid, and high elements to be in355 // ascending order, we'll use mid as our pivot.356 QSortArrange
                                    
                                      (keys, items, low, mid, comparer);357 if (QSortArrange
                                     
                                       (keys, items, mid, high, comparer))358 QSortArrange
                                      
                                        (keys, items, low, mid, comparer);359 360 key = keys[mid];361 gcmp = key as IComparable
                                       
                                        ;362 cmp = key as IComparable;363 364 // since we've already guaranteed that lo <= mid and mid <= hi,365 // we can skip comparing them again.366 k = high - 1;367 i = low + 1;368 369 do {370 // Move the walls in371 if (comparer != null) {372 // find the first element with a value >= pivot value373 while (i < k && comparer.Compare (key, keys[i]) > 0)374 i++;375 376 // find the last element with a value <= pivot value377 while (k > i && comparer.Compare (key, keys[k]) < 0)378 k--;379 } else {380 if (gcmp != null) {381 // find the first element with a value >= pivot value382 while (i < k && gcmp.CompareTo (keys[i]) > 0)383 i++;384 385 // find the last element with a value <= pivot value386 while (k > i && gcmp.CompareTo (keys[k]) < 0)387 k--;388 } else if (cmp != null) {389 // find the first element with a value >= pivot value390 while (i < k && cmp.CompareTo (keys[i]) > 0)391 i++;392 393 // find the last element with a value <= pivot value394 while (k > i && cmp.CompareTo (keys[k]) < 0)395 k--;396 } else {397 while (i < k && keys[i] == null)398 i++;399 400 while (k > i && keys[k] != null)401 k--;402 }403 }404 405 if (k <= i)406 break;407 408 swap
                                        
                                          (keys, items, i, k);409 410 i++;411 k--;412 } while (true);413 414 // push our partitions onto the stack, largest first415 // (to make sure we don't run out of stack space)416 if ((high - k) >= (k - low)) {417 if ((k + 1) < high) {418 stack[sp].high = high;419 stack[sp].low = k;420 sp++;421 }422 423 if ((k - 1) > low) {424 stack[sp].high = k;425 stack[sp].low = low;426 sp++;427 }428 } else {429 if ((k - 1) > low) {430 stack[sp].high = k;431 stack[sp].low = low;432 sp++;433 }434 435 if ((k + 1) < high) {436 stack[sp].high = high;437 stack[sp].low = k;438 sp++;439 }440 }441 } while (sp > 0);442 }443 444 // Specialized version for items==null445 unsafe static void qsort
                                         
                                           (K [] keys, int low0, int high0, IComparer
                                          
                                            comparer)446 {447 QSortStack* stack = stackalloc QSortStack [32];448 const int QSORT_THRESHOLD = 7;449 int high, low, mid, i, k;450 IComparable
                                           
                                             gcmp;451 IComparable cmp;452 int sp = 1;453 K key;454 455 // initialize our stack456 stack[0].high = high0;457 stack[0].low = low0;458 459 do {460 // pop the stack461 sp--;462 high = stack[sp].high;463 low = stack[sp].low;464 465 if ((low + QSORT_THRESHOLD) > high) {466 // switch to insertion sort467 for (i = low + 1; i <= high; i++) {468 for (k = i; k > low; k--) {469 // if keys[k] >= keys[k-1], break470 if (comparer != null) {471 if (comparer.Compare (keys[k], keys[k-1]) >= 0)472 break;473 } else {474 if (keys[k-1] == null)475 break;476 477 if (keys[k] != null) {478 gcmp = keys[k] as IComparable
                                            
                                             ;479 cmp = keys[k] as IComparable;480 if (gcmp != null) {481 if (gcmp.CompareTo (keys[k-1]) >= 0)482 break;483 } else {484 if (cmp.CompareTo (keys[k-1]) >= 0)485 break;486 }487 }488 }489 490 swap
                                             
                                               (keys, k - 1, k);491 }492 }493 494 continue;495 }496 497 // calculate the middle element498 mid = low + ((high - low) / 2);499 500 // once we re-order the low, mid, and high elements to be in501 // ascending order, we'll use mid as our pivot.502 QSortArrange
                                              
                                                (keys, low, mid, comparer);503 if (QSortArrange
                                               
                                                 (keys, mid, high, comparer))504 QSortArrange
                                                
                                                  (keys, low, mid, comparer);505 506 key = keys[mid];507 gcmp = key as IComparable
                                                 
                                                  ;508 cmp = key as IComparable;509 510 // since we've already guaranteed that lo <= mid and mid <= hi,511 // we can skip comparing them again.512 k = high - 1;513 i = low + 1;514 515 do {516 // Move the walls in517 if (comparer != null) {518 // find the first element with a value >= pivot value519 while (i < k && comparer.Compare (key, keys[i]) > 0)520 i++;521 522 // find the last element with a value <= pivot value523 while (k > i && comparer.Compare (key, keys[k]) < 0)524 k--;525 } else {526 if (gcmp != null) {527 // find the first element with a value >= pivot value528 while (i < k && gcmp.CompareTo (keys[i]) > 0)529 i++;530 531 // find the last element with a value <= pivot value532 while (k > i && gcmp.CompareTo (keys[k]) < 0)533 k--;534 } else if (cmp != null) {535 // find the first element with a value >= pivot value536 while (i < k && cmp.CompareTo (keys[i]) > 0)537 i++;538 539 // find the last element with a value <= pivot value540 while (k > i && cmp.CompareTo (keys[k]) < 0)541 k--;542 } else {543 while (i < k && keys[i] == null)544 i++;545 546 while (k > i && keys[k] != null)547 k--;548 }549 }550 551 if (k <= i)552 break;553 554 swap
                                                  
                                                    (keys, i, k);555 556 i++;557 k--;558 } while (true);559 560 // push our partitions onto the stack, largest first561 // (to make sure we don't run out of stack space)562 if ((high - k) >= (k - low)) {563 if ((k + 1) < high) {564 stack[sp].high = high;565 stack[sp].low = k;566 sp++;567 }568 569 if ((k - 1) > low) {570 stack[sp].high = k;571 stack[sp].low = low;572 sp++;573 }574 } else {575 if ((k - 1) > low) {576 stack[sp].high = k;577 stack[sp].low = low;578 sp++;579 }580 581 if ((k + 1) < high) {582 stack[sp].high = high;583 stack[sp].low = k;584 sp++;585 }586 }587 } while (sp > 0);588 }589 590 static bool QSortArrange
                                                   
                                                     (T [] array, int lo, int hi, Comparison
                                                    
                                                      compare)591 {592 if (array[lo] != null) {593 if (array[hi] == null || compare (array[hi], array[lo]) < 0) {594 swap
                                                     
                                                       (array, lo, hi);595 return true;596 }597 }598 599 return false;600 }601 602 unsafe static void qsort
                                                      
                                                        (T [] array, int low0, int high0, Comparison
                                                       
                                                         compare)603 {604 QSortStack* stack = stackalloc QSortStack [32];605 const int QSORT_THRESHOLD = 7;606 int high, low, mid, i, k;607 int sp = 1;608 T key;609 610 // initialize our stack611 stack[0].high = high0;612 stack[0].low = low0;613 614 do {615 // pop the stack616 sp--;617 high = stack[sp].high;618 low = stack[sp].low;619 620 if ((low + QSORT_THRESHOLD) > high) {621 // switch to insertion sort622 for (i = low + 1; i <= high; i++) {623 for (k = i; k > low; k--) {624 if (compare (array[k], array[k-1]) >= 0)625 break;626 627 swap
                                                        
                                                          (array, k - 1, k);628 }629 }630 631 continue;632 }633 634 // calculate the middle element635 mid = low + ((high - low) / 2);636 637 // once we re-order the lo, mid, and hi elements to be in638 // ascending order, we'll use mid as our pivot.639 QSortArrange
                                                         
                                                           (array, low, mid, compare);640 if (QSortArrange
                                                          
                                                            (array, mid, high, compare))641 QSortArrange
                                                           
                                                             (array, low, mid, compare);642 643 key = array[mid];644 645 // since we've already guaranteed that lo <= mid and mid <= hi,646 // we can skip comparing them again647 k = high - 1;648 i = low + 1;649 650 do {651 // Move the walls in652 if (key != null) {653 // find the first element with a value >= pivot value654 while (i < k && compare (key, array[i]) > 0)655 i++;656 657 // find the last element with a value <= pivot value658 while (k > i && compare (key, array[k]) < 0)659 k--;660 } else {661 while (i < k && array[i] == null)662 i++;663 664 while (k > i && array[k] != null)665 k--;666 }667 668 if (k <= i)669 break;670 671 swap
                                                            
                                                              (array, i, k);672 673 i++;674 k--;675 } while (true);676 677 // push our partitions onto the stack, largest first678 // (to make sure we don't run out of stack space)679 if ((high - k) >= (k - low)) {680 if ((k + 1) < high) {681 stack[sp].high = high;682 stack[sp].low = k;683 sp++;684 }685 686 if ((k - 1) > low) {687 stack[sp].high = k;688 stack[sp].low = low;689 sp++;690 }691 } else {692 if ((k - 1) > low) {693 stack[sp].high = k;694 stack[sp].low = low;695 sp++;696 }697 698 if ((k + 1) < high) {699 stack[sp].high = high;700 stack[sp].low = k;701 sp++;702 }703 }704 } while (sp > 0);705 }