Scortch/sort.c
/// Merge sort that doubles the width at each iteration instead of halving at each descent
Merge sort that doubles the width at each iteration instead of halving at each descent
Merge sort that doubles the width at each iteration instead of halving at each descent
void bottomUpMergeSort(void *array, size_t count, size_t size, size_t width, void *buffer, size_t space, struct SortingStatistics *statistics, Compare compare, void *context) {
	size_t index;
	if ( width > 1 ) {
		index = 0;
		while ( index + width <= count ) {
			binaryInsertionSort(array + index * size, width, size, 1, buffer, statistics, compare, context);
			index += width;
		}
		if ( index + 1 < count ) {
			binaryInsertionSort(array + index * size, count - index, size, 1, buffer, statistics, compare, context);
		}
	} else {
		width = 1;
	}
	while ( width < count ) {
		index = 0;
		while ( index + width * 2 <= count ) {
			mergeSorted(array + index * size, width * 2, width, size, buffer, space, statistics, compare, context);
			index += width * 2;
		}
		if ( index + width < count ) {
			mergeSorted(array + index * size, count - index, width, size, buffer, space, statistics, compare, context);
		}
		width *= 2;
	}
}
void bottomUpMergeSort ( void * array , size_t count , size_t size , size_t width , void * buffer , size_t space , struct SortingStatistics * statistics , Compare compare , void * context ) { size_t index ; if ( width > 1 ) { index = 0 ; while ( index + width <= count ) { binaryInsertionSort ( array + index * size , width , size , 1 , buffer , statistics , compare , context ) ; index += width ; } if ( index + 1 < count ) { binaryInsertionSort ( array + index * size , count - index , size , 1 , buffer , statistics , compare , context ) ; } } else { width = 1 ; } while ( width < count ) { index = 0 ; while ( index + width * 2 <= count ) { mergeSorted ( array + index * size , width * 2 , width , size , buffer , space , statistics , compare , context ) ; index += width * 2 ; } if ( index + width < count ) { mergeSorted ( array + index * size , count - index , width , size , buffer , space , statistics , compare , context ) ; } width *= 2 ; } }
Merge sort that doubles the width at each iteration instead of halving at each descent
Merge sort that doubles the width at each iteration instead of halving at each descent