1 unsafe static void qsort<T, U> (T[] keys, U[] items, int low0, int high0) where T : IComparable<T>
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<T, U> (keys, items, low, mid);
43 if (QSortArrange<T, U> (keys, items, mid, high))
44 QSortArrange<T, U> (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==null
110 unsafe static void qsort<T> (T[] keys, int low0, int high0) where T : IComparable<T>
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 stack
119 stack[0].high = high0;
120 stack[0].low = low0;
121
122 do {
123 // pop the stack
124 sp--;
125 high = stack[sp].high;
126 low = stack[sp].low;
127
128 if ((low + QSORT_THRESHOLD) > high) {
129 // switch to insertion sort
130 for (i = low + 1; i <= high; i++) {
131 for (k = i; k > low; k--) {
132 // if keys[k] >= keys[k-1], break
133 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 element
147 mid = low + ((high - low) / 2);
148
149 // once we re-order the lo, mid, and hi elements to be in
150 // ascending order, we'll use mid as our pivot.
151 QSortArrange<T> (keys, low, mid);
152 if (QSortArrange<T> (keys, mid, high))
153 QSortArrange<T> (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 again
159 k = high - 1;
160 i = low + 1;
161
162 do {
163 if (key != null) {
164 // find the first element with a value >= pivot value
165 while (i < k && key.CompareTo (keys[i]) > 0)
166 i++;
167
168 // find the last element with a value <= pivot value
169 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 first
189 // (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, V> (K [] keys, V [] items, int lo, int hi, IComparer<K> comparer)
219 {
220 IComparable<K> gcmp;
221 IComparable cmp;
222
223 if (comparer != null) {
224 if (comparer.Compare (keys[hi], keys[lo]) < 0) {
225 swap<K, V> (keys, items, lo, hi);
226 return true;
227 }
228 } else if (keys[lo] != null) {
229 if (keys[hi] == null) {
230 swap<K, V> (keys, items, lo, hi);
231 return true;
232 }
233
234 gcmp = keys[hi] as IComparable<K>;
235 if (gcmp != null) {
236 if (gcmp.CompareTo (keys[lo]) < 0) {
237 swap<K, V> (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<K, V> (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==null
259 static bool QSortArrange<K> (K [] keys, int lo, int hi, IComparer<K> comparer)
260 {
261 IComparable<K> gcmp;
262 IComparable cmp;
263
264 if (comparer != null) {
265 if (comparer.Compare (keys[hi], keys[lo]) < 0) {
266 swap<K> (keys, lo, hi);
267 return true;
268 }
269 } else if (keys[lo] != null) {
270 if (keys[hi] == null) {
271 swap<K> (keys, lo, hi);
272 return true;
273 }
274
275 gcmp = keys[hi] as IComparable<K>;
276 if (gcmp != null) {
277 if (gcmp.CompareTo (keys[lo]) < 0) {
278 swap<K> (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<K> (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, V> (K [] keys, V [] items, int low0, int high0, IComparer<K> comparer)
300 {
301 QSortStack* stack = stackalloc QSortStack [32];
302 const int QSORT_THRESHOLD = 7;
303 int high, low, mid, i, k;
304 IComparable<K> gcmp;
305 IComparable cmp;
306 int sp = 1;
307 K key;
308
309 // initialize our stack
310 stack[0].high = high0;
311 stack[0].low = low0;
312
313 do {
314 // pop the stack
315 sp--;
316 high = stack[sp].high;
317 low = stack[sp].low;
318
319 if ((low + QSORT_THRESHOLD) > high) {
320 // switch to insertion sort
321 for (i = low + 1; i <= high; i++) {
322 for (k = i; k > low; k--) {
323 // if keys[k] >= keys[k-1], break
324 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<K>;
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<K, V> (keys, items, k - 1, k);
345 }
346 }
347
348 continue;
349 }
350
351 // calculate the middle element
352 mid = low + ((high - low) / 2);
353
354 // once we re-order the low, mid, and high elements to be in
355 // ascending order, we'll use mid as our pivot.
356 QSortArrange<K, V> (keys, items, low, mid, comparer);
357 if (QSortArrange<K, V> (keys, items, mid, high, comparer))
358 QSortArrange<K, V> (keys, items, low, mid, comparer);
359
360 key = keys[mid];
361 gcmp = key as IComparable<K>;
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 in
371 if (comparer != null) {
372 // find the first element with a value >= pivot value
373 while (i < k && comparer.Compare (key, keys[i]) > 0)
374 i++;
375
376 // find the last element with a value <= pivot value
377 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 value
382 while (i < k && gcmp.CompareTo (keys[i]) > 0)
383 i++;
384
385 // find the last element with a value <= pivot value
386 while (k > i && gcmp.CompareTo (keys[k]) < 0)
387 k--;
388 } else if (cmp != null) {
389 // find the first element with a value >= pivot value
390 while (i < k && cmp.CompareTo (keys[i]) > 0)
391 i++;
392
393 // find the last element with a value <= pivot value
394 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<K, V> (keys, items, i, k);
409
410 i++;
411 k--;
412 } while (true);
413
414 // push our partitions onto the stack, largest first
415 // (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==null
445 unsafe static void qsort<K> (K [] keys, int low0, int high0, IComparer<K> comparer)
446 {
447 QSortStack* stack = stackalloc QSortStack [32];
448 const int QSORT_THRESHOLD = 7;
449 int high, low, mid, i, k;
450 IComparable<K> gcmp;
451 IComparable cmp;
452 int sp = 1;
453 K key;
454
455 // initialize our stack
456 stack[0].high = high0;
457 stack[0].low = low0;
458
459 do {
460 // pop the stack
461 sp--;
462 high = stack[sp].high;
463 low = stack[sp].low;
464
465 if ((low + QSORT_THRESHOLD) > high) {
466 // switch to insertion sort
467 for (i = low + 1; i <= high; i++) {
468 for (k = i; k > low; k--) {
469 // if keys[k] >= keys[k-1], break
470 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<K>;
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<K> (keys, k - 1, k);
491 }
492 }
493
494 continue;
495 }
496
497 // calculate the middle element
498 mid = low + ((high - low) / 2);
499
500 // once we re-order the low, mid, and high elements to be in
501 // ascending order, we'll use mid as our pivot.
502 QSortArrange<K> (keys, low, mid, comparer);
503 if (QSortArrange<K> (keys, mid, high, comparer))
504 QSortArrange<K> (keys, low, mid, comparer);
505
506 key = keys[mid];
507 gcmp = key as IComparable<K>;
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 in
517 if (comparer != null) {
518 // find the first element with a value >= pivot value
519 while (i < k && comparer.Compare (key, keys[i]) > 0)
520 i++;
521
522 // find the last element with a value <= pivot value
523 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 value
528 while (i < k && gcmp.CompareTo (keys[i]) > 0)
529 i++;
530
531 // find the last element with a value <= pivot value
532 while (k > i && gcmp.CompareTo (keys[k]) < 0)
533 k--;
534 } else if (cmp != null) {
535 // find the first element with a value >= pivot value
536 while (i < k && cmp.CompareTo (keys[i]) > 0)
537 i++;
538
539 // find the last element with a value <= pivot value
540 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<K> (keys, i, k);
555
556 i++;
557 k--;
558 } while (true);
559
560 // push our partitions onto the stack, largest first
561 // (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> (T [] array, int lo, int hi, Comparison<T> compare)
591 {
592 if (array[lo] != null) {
593 if (array[hi] == null || compare (array[hi], array[lo]) < 0) {
594 swap<T> (array, lo, hi);
595 return true;
596 }
597 }
598
599 return false;
600 }
601
602 unsafe static void qsort<T> (T [] array, int low0, int high0, Comparison<T> 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 stack
611 stack[0].high = high0;
612 stack[0].low = low0;
613
614 do {
615 // pop the stack
616 sp--;
617 high = stack[sp].high;
618 low = stack[sp].low;
619
620 if ((low + QSORT_THRESHOLD) > high) {
621 // switch to insertion sort
622 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<T> (array, k - 1, k);
628 }
629 }
630
631 continue;
632 }
633
634 // calculate the middle element
635 mid = low + ((high - low) / 2);
636
637 // once we re-order the lo, mid, and hi elements to be in
638 // ascending order, we'll use mid as our pivot.
639 QSortArrange<T> (array, low, mid, compare);
640 if (QSortArrange<T> (array, mid, high, compare))
641 QSortArrange<T> (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 again
647 k = high - 1;
648 i = low + 1;
649
650 do {
651 // Move the walls in
652 if (key != null) {
653 // find the first element with a value >= pivot value
654 while (i < k && compare (key, array[i]) > 0)
655 i++;
656
657 // find the last element with a value <= pivot value
658 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<T> (array, i, k);
672
673 i++;
674 k--;
675 } while (true);
676
677 // push our partitions onto the stack, largest first
678 // (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 }