My benchmarks could be improved but however I found that Shivers' sort
and adaptive Shivers' sort (aka Jugé's sort) performs better than
Tim's sort.
it can be done easily by switching the
main natural merge strategy like I did here :
https://github.com/LLyaudet/TSODLULS/commit/2968c4b4ca58ae794157dc9636ed87017e5f7a17
The relevant code is not very long :
/**
* This strategy is from ShiversSort:
* see the research report by Olin Shivers, Georgia Institute of
Technology, 2002.
* It uses bitwise tricks to check condition on floor of logarithms in
base 2 of runs lengths.
* When I benchmark it, it is slightly faster than Tim's sort strategy.
*/
#define TSODLULS_natural_merge_main_strategy__Shivers_sort \
while(merge_state.i_run_instances_count > 1){\
size_t i_merge_at = merge_state.i_run_instances_count - 2;\
size_t i_order_of_magnitude =
merge_state.arr_run_instances[i_merge_at + 1].i_length;\
if(i_order_of_magnitude < ((~i_order_of_magnitude) &
merge_state.arr_run_instances[i_merge_at].i_length) ){\
break;\
}\
i_compare_result = TSODLULS_MERGE_TWO_RUNS(&merge_state, i_merge_at);\
if(i_compare_result != 0){\
goto clean_and_return_error;\
}\
}\
/**
* This strategy is from AdaptiveShiversSort:
* see the articles by Vincent Jugé, for example 1024 Bulletin de la
SIF, avril 2020, in French,
* or the preprint on arXiv or SODA 2020 proceedings.
* It uses bitwise tricks to check condition on floor of logarithms in
base 2 of runs lengths.
* When I benchmark it, it is slightly faster than Tim's sort strategy.
* Despite its ressemblance with Shivers's sort,
* the distinct properties of this strategy make that JugéSort would
probably be a better name than AdaptiveShiversSort,
* or an even better name for the whole algorithm should be
TimShiversJugéSort and I must have missed many names ;)
* With AdaptiveShiversSort we avoid 'é' and diacritics in function names ;P
*/
#define TSODLULS_natural_merge_main_strategy__adaptive_Shivers_sort \
while(merge_state.i_run_instances_count > 2){\
size_t i_merge_at = merge_state.i_run_instances_count - 3;\
size_t i_order_of_magnitude =
merge_state.arr_run_instances[i_merge_at + 1].i_length |
merge_state.arr_run_instances[i_merge_at + 2].i_length;\
if(i_order_of_magnitude < ((~i_order_of_magnitude) &
merge_state.arr_run_instances[i_merge_at].i_length) ){\
break;\
}\
i_compare_result = TSODLULS_MERGE_TWO_RUNS(&merge_state, i_merge_at);\
if(i_compare_result != 0){\
goto clean_and_return_error;\
}\
}\
I will try to provide a patch before the end of the week. |