Bio/Cluster/mysort.h
/* Insertion sort is best when the array is small*/
Insertion sort is best when the array is small
Insertion sort is best when the array is small
inline void
insertion_sort_index(const double a[], int index[], int l, int r)
{
	if (r <= l) return;
	int i, j, current_index;
	double value;
	i = l; j = r;
	value = a[index[(l + r) >> 1]];
	while (i <= j) {
		while (a[index[i]] < value) i++;
		while (a[index[j]] > value) j--;
		if (i <= j) {
			swap_int(index[i], index[j]);
			i++;
			j--;
		}
	}
	for (i = l + 1; i <= r; i++) {
		j = i - 1;
		value = a[index[i]];
		current_index = index[i];
		while (j >= l && a[index[j]] > value) {
			index[j + 1] = index[j];
			j--;
		}
		index[j + 1] = current_index;
	}
}
inline void insertion_sort_index ( const double a [ ] , int index [ ] , int l , int r ) { if ( r <= l ) return ; int i , j , current_index ; double value ; i = l ; j = r ; value = a [ index [ ( l + r ) >> 1 ] ] ; while ( i <= j ) { while ( a [ index [ i ] ] < value ) i ++ ; while ( a [ index [ j ] ] > value ) j -- ; if ( i <= j ) { swap_int ( index [ i ] , index [ j ] ) ; i ++ ; j -- ; } } for ( i = l + 1 ; i <= r ; i ++ ) { j = i - 1 ; value = a [ index [ i ] ] ; current_index = index [ i ] ; while ( j >= l && a [ index [ j ] ] > value ) { index [ j + 1 ] = index [ j ] ; j -- ; } index [ j + 1 ] = current_index ; } }
Insertion sort is best when the array is small
Insertion sort is best when the array is small
/* Performing 1 quicksort loops increase performance by 20-30% on random data,
	 * and completely eliminate worst-case scenario. It's slower when the array is
	 * sorted, but in that case the sort time is already tiny.
	 */