Hello, I developed a C sorting algorithms library that currently has a few dozens of algorithms and thousands of variants when choosing parameters (like threshold for switching to insertion sort, etc.). (I compile each variant on demand in custom tests to avoid having a bloated source file.) 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. I don't know if it will still be true with the benchmarks in Python. If you're open to the idea that maybe Tim's sort can be improved and are willing to benchmark it, it can be done easily by switching the main natural merge strategy like I did here : https://github.com/LLyaudet/TSODLULS/commit/2968c4b4ca58ae794157dc9636ed8701... 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;\ }\ }\ In my library the merge strategy is a parameter and I switch its macro when compiling competitors algorithms on demand. I hope it may help. Thanks for your time. If you want to look further at my library, it works with gcc and glibc. I have not tested it on other platforms and whilst I have no compilation warning on my personal dev laptop, I do have one when I run it on the laptop I'm currently writing this email. The tests passes nevertheless. Best regards, Laurent Lyaudet