Scortch/sort.c
/// Self balancing quick sort that use an alternate sorting algorithm on affected regions after several pivots in a row are imbalanced
Self balancing quick sort that use an alternate sorting algorithm on affected regions after several pivots in a row are imbalanced
Self balancing quick sort that use an alternate sorting algorithm on affected regions after several pivots in a row are imbalanced
void balancingQuickSort(void *array, size_t count, size_t size, unsigned imbalances, void *temporary, struct SortingStatistics *statistics, Compare compare, void *context) {
	if ( count < 2 ) {
		return;
	} else if ( count < 16 ) {	
		binaryInsertionSort(array, count, size, 1, temporary, statistics, compare, context);
	} else if ( imbalances > 4 ) {
		heapSort(array, count, size, temporary, statistics, compare, context);
	} else {
		size_t pivot = quickPartition(array, count, size, temporary, statistics, compare, context);
		size_t ratio = 12;
		imbalances = count > ratio * (count - pivot - 1 < pivot ? count - pivot - 1 : pivot) ? imbalances + 1 : 0;
		balancingQuickSort(array, pivot, size, imbalances, temporary, statistics, compare, context);
		balancingQuickSort(array + pivot * size, count - pivot, size, imbalances, temporary, statistics, compare, context);
	}
}
void balancingQuickSort ( void * array , size_t count , size_t size , unsigned imbalances , void * temporary , struct SortingStatistics * statistics , Compare compare , void * context ) { if ( count < 2 ) { return ; } else if ( count < 16 ) { binaryInsertionSort ( array , count , size , 1 , temporary , statistics , compare , context ) ; } else if ( imbalances > 4 ) { heapSort ( array , count , size , temporary , statistics , compare , context ) ; } else { size_t pivot = quickPartition ( array , count , size , temporary , statistics , compare , context ) ; size_t ratio = 12 ; imbalances = count > ratio * ( count - pivot - 1 < pivot ? count - pivot - 1 : pivot ) ? imbalances + 1 : 0 ; balancingQuickSort ( array , pivot , size , imbalances , temporary , statistics , compare , context ) ; balancingQuickSort ( array + pivot * size , count - pivot , size , imbalances , temporary , statistics , compare , context ) ; } }
Self balancing quick sort that use an alternate sorting algorithm on affected regions after several pivots in a row are imbalanced
Self balancing quick sort that use an alternate sorting algorithm on affected regions after several pivots in a row are imbalanced
//	higher threshold will decrease comparisons and increase assignments