unsafe static void qsort<T, U> (T[] keys, U[] items, int low0, int high0) where T : IComparable<T>
{
QSortStack* stack = stackalloc QSortStack [];
const int QSORT_THRESHOLD = ;
int high, low, mid, i, k;
int sp = ;
T key;
// initialize our stack
stack[].high = high0;
stack[].low = low0;
do {
// pop the stack
sp--;
high = stack[sp].high;
low = stack[sp].low;
if ((low + QSORT_THRESHOLD) > high) {
// switch to insertion sort
for (i = low + ; i <= high; i++) {
for (k = i; k > low; k--) {
// if keys[k] >= keys[k-1], break
if (keys[k-] == null)
break;
if (keys[k] != null && keys[k].CompareTo (keys[k-]) >= )
break;
swap (keys, items, k - , k);
}
}
continue;
}
// calculate the middle element
mid = low + ((high - low) / );
// once we re-order the lo, mid, and hi elements to be in
// ascending order, we'll use mid as our pivot.
QSortArrange<T, U> (keys, items, low, mid);
if (QSortArrange<T, U> (keys, items, mid, high))
QSortArrange<T, U> (keys, items, low, mid);
key = keys[mid];
// since we've already guaranteed that lo <= mid and mid <= hi,
// we can skip comparing them again
k = high - ;
i = low + ;
do {
if (key != null) {
// find the first element with a value >= pivot value
while (i < k && key.CompareTo (keys[i]) > )
i++;
// find the last element with a value <= pivot value
while (k > i && key.CompareTo (keys[k]) < )
k--;
} else {
while (i < k && keys[i] == null)
i++;
while (k > i && keys[k] != null)
k--;
}
if (k <= i)
break;
swap (keys, items, i, k);
i++;
k--;
} while (true);
// push our partitions onto the stack, largest first
// (to make sure we don't run out of stack space)
if ((high - k) >= (k - low)) {
if ((k + ) < high) {
stack[sp].high = high;
stack[sp].low = k;
sp++;
}
if ((k - ) > low) {
stack[sp].high = k;
stack[sp].low = low;
sp++;
}
} else {
if ((k - ) > low) {
stack[sp].high = k;
stack[sp].low = low;
sp++;
}
if ((k + ) < high) {
stack[sp].high = high;
stack[sp].low = k;
sp++;
}
}
} while (sp > );
}
// Specialized version for items==null
unsafe static void qsort<T> (T[] keys, int low0, int high0) where T : IComparable<T>
{
QSortStack* stack = stackalloc QSortStack [];
const int QSORT_THRESHOLD = ;
int high, low, mid, i, k;
int sp = ;
T key;
// initialize our stack
stack[].high = high0;
stack[].low = low0;
do {
// pop the stack
sp--;
high = stack[sp].high;
low = stack[sp].low;
if ((low + QSORT_THRESHOLD) > high) {
// switch to insertion sort
for (i = low + ; i <= high; i++) {
for (k = i; k > low; k--) {
// if keys[k] >= keys[k-1], break
if (keys[k-] == null)
break;
if (keys[k] != null && keys[k].CompareTo (keys[k-]) >= )
break;
swap (keys, k - , k);
}
}
continue;
}
// calculate the middle element
mid = low + ((high - low) / );
// once we re-order the lo, mid, and hi elements to be in
// ascending order, we'll use mid as our pivot.
QSortArrange<T> (keys, low, mid);
if (QSortArrange<T> (keys, mid, high))
QSortArrange<T> (keys, low, mid);
key = keys[mid];
// since we've already guaranteed that lo <= mid and mid <= hi,
// we can skip comparing them again
k = high - ;
i = low + ;
do {
if (key != null) {
// find the first element with a value >= pivot value
while (i < k && key.CompareTo (keys[i]) > )
i++;
// find the last element with a value <= pivot value
while (k >= i && key.CompareTo (keys[k]) < )
k--;
} else {
while (i < k && keys[i] == null)
i++;
while (k >= i && keys[k] != null)
k--;
}
if (k <= i)
break;
swap (keys, i, k);
i++;
k--;
} while (true);
// push our partitions onto the stack, largest first
// (to make sure we don't run out of stack space)
if ((high - k) >= (k - low)) {
if ((k + ) < high) {
stack[sp].high = high;
stack[sp].low = k;
sp++;
}
if ((k - ) > low) {
stack[sp].high = k;
stack[sp].low = low;
sp++;
}
} else {
if ((k - ) > low) {
stack[sp].high = k;
stack[sp].low = low;
sp++;
}
if ((k + ) < high) {
stack[sp].high = high;
stack[sp].low = k;
sp++;
}
}
} while (sp > );
}
static bool QSortArrange<K, V> (K [] keys, V [] items, int lo, int hi, IComparer<K> comparer)
{
IComparable<K> gcmp;
IComparable cmp;
if (comparer != null) {
if (comparer.Compare (keys[hi], keys[lo]) < ) {
swap<K, V> (keys, items, lo, hi);
return true;
}
} else if (keys[lo] != null) {
if (keys[hi] == null) {
swap<K, V> (keys, items, lo, hi);
return true;
}
gcmp = keys[hi] as IComparable<K>;
if (gcmp != null) {
if (gcmp.CompareTo (keys[lo]) < ) {
swap<K, V> (keys, items, lo, hi);
return true;
}
return false;
}
cmp = keys[hi] as IComparable;
if (cmp != null) {
if (cmp.CompareTo (keys[lo]) < ) {
swap<K, V> (keys, items, lo, hi);
return true;
}
return false;
}
}
return false;
}
// Specialized version for items==null
static bool QSortArrange<K> (K [] keys, int lo, int hi, IComparer<K> comparer)
{
IComparable<K> gcmp;
IComparable cmp;
if (comparer != null) {
if (comparer.Compare (keys[hi], keys[lo]) < ) {
swap<K> (keys, lo, hi);
return true;
}
} else if (keys[lo] != null) {
if (keys[hi] == null) {
swap<K> (keys, lo, hi);
return true;
}
gcmp = keys[hi] as IComparable<K>;
if (gcmp != null) {
if (gcmp.CompareTo (keys[lo]) < ) {
swap<K> (keys, lo, hi);
return true;
}
return false;
}
cmp = keys[hi] as IComparable;
if (cmp != null) {
if (cmp.CompareTo (keys[lo]) < ) {
swap<K> (keys, lo, hi);
return true;
}
return false;
}
}
return false;
}
unsafe static void qsort<K, V> (K [] keys, V [] items, int low0, int high0, IComparer<K> comparer)
{
QSortStack* stack = stackalloc QSortStack [];
const int QSORT_THRESHOLD = ;
int high, low, mid, i, k;
IComparable<K> gcmp;
IComparable cmp;
int sp = ;
K key;
// initialize our stack
stack[].high = high0;
stack[].low = low0;
do {
// pop the stack
sp--;
high = stack[sp].high;
low = stack[sp].low;
if ((low + QSORT_THRESHOLD) > high) {
// switch to insertion sort
for (i = low + ; i <= high; i++) {
for (k = i; k > low; k--) {
// if keys[k] >= keys[k-1], break
if (comparer != null) {
if (comparer.Compare (keys[k], keys[k-]) >= )
break;
} else {
if (keys[k-] == null)
break;
if (keys[k] != null) {
gcmp = keys[k] as IComparable<K>;
cmp = keys[k] as IComparable;
if (gcmp != null) {
if (gcmp.CompareTo (keys[k-]) >= )
break;
} else {
if (cmp.CompareTo (keys[k-]) >= )
break;
}
}
}
swap<K, V> (keys, items, k - , k);
}
}
continue;
}
// calculate the middle element
mid = low + ((high - low) / );
// once we re-order the low, mid, and high elements to be in
// ascending order, we'll use mid as our pivot.
QSortArrange<K, V> (keys, items, low, mid, comparer);
if (QSortArrange<K, V> (keys, items, mid, high, comparer))
QSortArrange<K, V> (keys, items, low, mid, comparer);
key = keys[mid];
gcmp = key as IComparable<K>;
cmp = key as IComparable;
// since we've already guaranteed that lo <= mid and mid <= hi,
// we can skip comparing them again.
k = high - ;
i = low + ;
do {
// Move the walls in
if (comparer != null) {
// find the first element with a value >= pivot value
while (i < k && comparer.Compare (key, keys[i]) > )
i++;
// find the last element with a value <= pivot value
while (k > i && comparer.Compare (key, keys[k]) < )
k--;
} else {
if (gcmp != null) {
// find the first element with a value >= pivot value
while (i < k && gcmp.CompareTo (keys[i]) > )
i++;
// find the last element with a value <= pivot value
while (k > i && gcmp.CompareTo (keys[k]) < )
k--;
} else if (cmp != null) {
// find the first element with a value >= pivot value
while (i < k && cmp.CompareTo (keys[i]) > )
i++;
// find the last element with a value <= pivot value
while (k > i && cmp.CompareTo (keys[k]) < )
k--;
} else {
while (i < k && keys[i] == null)
i++;
while (k > i && keys[k] != null)
k--;
}
}
if (k <= i)
break;
swap<K, V> (keys, items, i, k);
i++;
k--;
} while (true);
// push our partitions onto the stack, largest first
// (to make sure we don't run out of stack space)
if ((high - k) >= (k - low)) {
if ((k + ) < high) {
stack[sp].high = high;
stack[sp].low = k;
sp++;
}
if ((k - ) > low) {
stack[sp].high = k;
stack[sp].low = low;
sp++;
}
} else {
if ((k - ) > low) {
stack[sp].high = k;
stack[sp].low = low;
sp++;
}
if ((k + ) < high) {
stack[sp].high = high;
stack[sp].low = k;
sp++;
}
}
} while (sp > );
}
// Specialized version for items==null
unsafe static void qsort<K> (K [] keys, int low0, int high0, IComparer<K> comparer)
{
QSortStack* stack = stackalloc QSortStack [];
const int QSORT_THRESHOLD = ;
int high, low, mid, i, k;
IComparable<K> gcmp;
IComparable cmp;
int sp = ;
K key;
// initialize our stack
stack[].high = high0;
stack[].low = low0;
do {
// pop the stack
sp--;
high = stack[sp].high;
low = stack[sp].low;
if ((low + QSORT_THRESHOLD) > high) {
// switch to insertion sort
for (i = low + ; i <= high; i++) {
for (k = i; k > low; k--) {
// if keys[k] >= keys[k-1], break
if (comparer != null) {
if (comparer.Compare (keys[k], keys[k-]) >= )
break;
} else {
if (keys[k-] == null)
break;
if (keys[k] != null) {
gcmp = keys[k] as IComparable<K>;
cmp = keys[k] as IComparable;
if (gcmp != null) {
if (gcmp.CompareTo (keys[k-]) >= )
break;
} else {
if (cmp.CompareTo (keys[k-]) >= )
break;
}
}
}
swap<K> (keys, k - , k);
}
}
continue;
}
// calculate the middle element
mid = low + ((high - low) / );
// once we re-order the low, mid, and high elements to be in
// ascending order, we'll use mid as our pivot.
QSortArrange<K> (keys, low, mid, comparer);
if (QSortArrange<K> (keys, mid, high, comparer))
QSortArrange<K> (keys, low, mid, comparer);
key = keys[mid];
gcmp = key as IComparable<K>;
cmp = key as IComparable;
// since we've already guaranteed that lo <= mid and mid <= hi,
// we can skip comparing them again.
k = high - ;
i = low + ;
do {
// Move the walls in
if (comparer != null) {
// find the first element with a value >= pivot value
while (i < k && comparer.Compare (key, keys[i]) > )
i++;
// find the last element with a value <= pivot value
while (k > i && comparer.Compare (key, keys[k]) < )
k--;
} else {
if (gcmp != null) {
// find the first element with a value >= pivot value
while (i < k && gcmp.CompareTo (keys[i]) > )
i++;
// find the last element with a value <= pivot value
while (k > i && gcmp.CompareTo (keys[k]) < )
k--;
} else if (cmp != null) {
// find the first element with a value >= pivot value
while (i < k && cmp.CompareTo (keys[i]) > )
i++;
// find the last element with a value <= pivot value
while (k > i && cmp.CompareTo (keys[k]) < )
k--;
} else {
while (i < k && keys[i] == null)
i++;
while (k > i && keys[k] != null)
k--;
}
}
if (k <= i)
break;
swap<K> (keys, i, k);
i++;
k--;
} while (true);
// push our partitions onto the stack, largest first
// (to make sure we don't run out of stack space)
if ((high - k) >= (k - low)) {
if ((k + ) < high) {
stack[sp].high = high;
stack[sp].low = k;
sp++;
}
if ((k - ) > low) {
stack[sp].high = k;
stack[sp].low = low;
sp++;
}
} else {
if ((k - ) > low) {
stack[sp].high = k;
stack[sp].low = low;
sp++;
}
if ((k + ) < high) {
stack[sp].high = high;
stack[sp].low = k;
sp++;
}
}
} while (sp > );
}
static bool QSortArrange<T> (T [] array, int lo, int hi, Comparison<T> compare)
{
if (array[lo] != null) {
if (array[hi] == null || compare (array[hi], array[lo]) < ) {
swap<T> (array, lo, hi);
return true;
}
}
return false;
}
unsafe static void qsort<T> (T [] array, int low0, int high0, Comparison<T> compare)
{
QSortStack* stack = stackalloc QSortStack [];
const int QSORT_THRESHOLD = ;
int high, low, mid, i, k;
int sp = ;
T key;
// initialize our stack
stack[].high = high0;
stack[].low = low0;
do {
// pop the stack
sp--;
high = stack[sp].high;
low = stack[sp].low;
if ((low + QSORT_THRESHOLD) > high) {
// switch to insertion sort
for (i = low + ; i <= high; i++) {
for (k = i; k > low; k--) {
if (compare (array[k], array[k-]) >= )
break;
swap<T> (array, k - , k);
}
}
continue;
}
// calculate the middle element
mid = low + ((high - low) / );
// once we re-order the lo, mid, and hi elements to be in
// ascending order, we'll use mid as our pivot.
QSortArrange<T> (array, low, mid, compare);
if (QSortArrange<T> (array, mid, high, compare))
QSortArrange<T> (array, low, mid, compare);
key = array[mid];
// since we've already guaranteed that lo <= mid and mid <= hi,
// we can skip comparing them again
k = high - ;
i = low + ;
do {
// Move the walls in
if (key != null) {
// find the first element with a value >= pivot value
while (i < k && compare (key, array[i]) > )
i++;
// find the last element with a value <= pivot value
while (k > i && compare (key, array[k]) < )
k--;
} else {
while (i < k && array[i] == null)
i++;
while (k > i && array[k] != null)
k--;
}
if (k <= i)
break;
swap<T> (array, i, k);
i++;
k--;
} while (true);
// push our partitions onto the stack, largest first
// (to make sure we don't run out of stack space)
if ((high - k) >= (k - low)) {
if ((k + ) < high) {
stack[sp].high = high;
stack[sp].low = k;
sp++;
}
if ((k - ) > low) {
stack[sp].high = k;
stack[sp].low = low;
sp++;
}
} else {
if ((k - ) > low) {
stack[sp].high = k;
stack[sp].low = low;
sp++;
}
if ((k + ) < high) {
stack[sp].high = high;
stack[sp].low = k;
sp++;
}
}
} while (sp > );
}
