3 ms·

This article doesn't really make it clear but the merge sort discussion is specifically about glibc's implementation of qsort(). glibc's qsort() and Wine's qsor

This article doesn't really make it clear but the merge sort discussion is specifically about glibc's implementation of qsort(). glibc's qsort() and Wine's qsort() are the only ones I know of that use merge sort to implement qsort(). Most implementations use quick sort. I recently did my own benchmarking on various qsort()s since I was trying to implement a faster one. The various BSDs and macOS qsort() are all faster than glibc at sorting integers and they don't allocate memory: https://github.com/ludocode/pottery/tree/master/examples/pottery/qsort https://github.com/ludocode/pottery/tree/master/examples/pot... Of course sorting is much faster if you can inline the comparator so a templated sort algorithm is always going to be faster than a function that takes a function pointer. But this does not require C++; it can be done in plain C. The templated intro_sort from Pottery (linked above) is competitive with std::sort, as are the excellent swensort/sort templates: https://github.com/swenson/sort https://github.com/swenson/sort

BeeOnRope 6y ago
Yes, you don't need C++ to get an inlined comparator, but C++ certainly makes it easier in the sense that you can get basically guaranteed inlining [1]. In the C case, your options are fewer, and often more reliant on optimization and the vagaries of the compiler. In particular, I tried to modify glibc's qsort to force inlining of the comparator, using both flatten and always_inline attributes, but failed probably because of the recursive nature of merge sort: the main sorting function is recursive, meaning it cannot be flattened without limit, which ends up inhibiting inlining of the comparator as well. It can definitely be made to work, but it's less automatic than C++ and compatators passed as template arguments. Of course, the "specialize everything" approach of C++ has plenty of downsides too! --- [1] Really, what you get is guaranteed specialization, and then inlining follows easily from that, if the compiler decides it is profitable to inline the small comparator into the sort function.

BeeOnRope 6y ago

Yes, you don't need C++ to get an inlined comparator, but C++ certainly makes it easier in the sense that you can get basically guaranteed inlining [1]. In the C case, your options are fewer, and often more reliant on optimization and the vagaries of the compiler. In particular, I tried to modify glibc's qsort to force inlining of the comparator, using both flatten and always_inline attributes, but failed probably because of the recursive nature of merge sort: the main sorting function is recursive, meaning it cannot be flattened without limit, which ends up inhibiting inlining of the comparator as well. It can definitely be made to work, but it's less automatic than C++ and compatators passed as template arguments. Of course, the "specialize everything" approach of C++ has plenty of downsides too! --- [1] Really, what you get is guaranteed specialization, and then inlining follows easily from that, if the compiler decides it is profitable to inline the small comparator into the sort function.