Bio/Cluster/mysort.h
/* This function choose a pivot, move all smaller elements to the left,
 * larger ones to the right, and put the pivot in its correct position.
 * It also checks for sorted/reverse-sorted array to speed-up special cases.
 */
This function choose a pivot, move all smaller elements to the left,
larger ones to the right, and put the pivot in its correct position.
It also checks for sorted/reverse-sorted array to speed-up special cases.
This function choose a pivot move all smaller elements to the left larger ones to the right and put the pivot in its correct position . It also checks for sorted / reverse - sorted array to speed - up special cases .
static void
fastsort_partition(double a[], const int left, const int right, int* first_end_ptr, int* second_start_ptr) {
	int low, high, i, pivot, mid;
	double value;
	int increasing = 1, decreasing = 1;
	if ((right - left) & 1) pivot = left + cheap_random() % (right - left);
	else pivot = median_index_of3(a, left, (left + right) >> 1, right);
	value = a[pivot];
	low = left; high = right;
	while (a[low] < value) {
		low++;
		decreasing = 0;
		if (a[low] < a[low - 1]) increasing = 0;
	}
	while (a[high] > value) {
		high--;
		decreasing = 0;
		if (a[high] > a[high + 1]) increasing = 0;
	}
	increasing &= a[high] >= a[low];
	decreasing &= a[high] <= a[low];
	if (increasing) {
		if ((right - left) & 1) {
			for (i = low + 1; i <= high; i++) if (a[i] < a[i - 1]) {
				increasing = 0;
				break;
			}
		}
		else {
			for (i = high; i >= low + 1; i--) if (a[i] < a[i - 1]) {
				increasing = 0;
				break;
			}
		}
		if (increasing) {	
			*first_end_ptr = INF;
			return;
		}
	}
	if (decreasing) {
		if ((right - left) & 1) {
			for (i = low + 1; i <= high; i++) if (a[i] > a[i - 1]) {
				decreasing = 0;
				break;
			}
		}
		else {
			for (i = high; i >= low + 1; i--) if (a[i] > a[i - 1]) {
				decreasing = 0;
				break;
			}
		}
		if (decreasing) {
			mid = (right - left + 1) >> 1;
			for (i = 0; i < mid; i++) swap_f64(a[left + i], a[right - i]);
			*first_end_ptr = INF;
			return;
		}
	}
	while (low <= high) {
		while (a[low] < value) low++;
		while (a[high] > value) high--;
		if (low <= high) {
			swap_f64(a[low], a[high]);
			low++;
			high--;
		}
	}
	*first_end_ptr = high;
	*second_start_ptr = low;
}
static void fastsort_partition ( double a [ ] , const int left , const int right , int * first_end_ptr , int * second_start_ptr ) { int low , high , i , pivot , mid ; double value ; int increasing = 1 , decreasing = 1 ; if ( ( right - left ) & 1 ) pivot = left + cheap_random ( ) % ( right - left ) ; else pivot = median_index_of3 ( a , left , ( left + right ) >> 1 , right ) ; value = a [ pivot ] ; low = left ; high = right ; while ( a [ low ] < value ) { low ++ ; decreasing = 0 ; if ( a [ low ] < a [ low - 1 ] ) increasing = 0 ; } while ( a [ high ] > value ) { high -- ; decreasing = 0 ; if ( a [ high ] > a [ high + 1 ] ) increasing = 0 ; } increasing &= a [ high ] >= a [ low ] ; decreasing &= a [ high ] <= a [ low ] ; if ( increasing ) { if ( ( right - left ) & 1 ) { for ( i = low + 1 ; i <= high ; i ++ ) if ( a [ i ] < a [ i - 1 ] ) { increasing = 0 ; break ; } } else { for ( i = high ; i >= low + 1 ; i -- ) if ( a [ i ] < a [ i - 1 ] ) { increasing = 0 ; break ; } } if ( increasing ) { * first_end_ptr = INF ; return ; } } if ( decreasing ) { if ( ( right - left ) & 1 ) { for ( i = low + 1 ; i <= high ; i ++ ) if ( a [ i ] > a [ i - 1 ] ) { decreasing = 0 ; break ; } } else { for ( i = high ; i >= low + 1 ; i -- ) if ( a [ i ] > a [ i - 1 ] ) { decreasing = 0 ; break ; } } if ( decreasing ) { mid = ( right - left + 1 ) >> 1 ; for ( i = 0 ; i < mid ; i ++ ) swap_f64 ( a [ left + i ] , a [ right - i ] ) ; * first_end_ptr = INF ; return ; } } while ( low <= high ) { while ( a [ low ] < value ) low ++ ; while ( a [ high ] > value ) high -- ; if ( low <= high ) { swap_f64 ( a [ low ] , a [ high ] ) ; low ++ ; high -- ; } } * first_end_ptr = high ; * second_start_ptr = low ; }
This function choose a pivot, move all smaller elements to the left,
 larger ones to the right, and put the pivot in its correct position.
This function choose a pivot move all smaller elements to the left larger ones to the right and put the pivot in its correct position .
/*******/ /* choose a random way to choose pivot, to prevent all possible worst-cases*/ /*******/ /* Skip through smaller values on left and larger values on right*/ /*******/ /* Resolve degenerate input cases */ /* Choose randomly looping from left->right or right->left. Prevents all possible worst-cases */ /* sorted */ /******/