Beating Up on Qsort (2019)

• pdqsort

  9 2,283 0.0 C++

  Pattern-defeating quicksort.

Just for fun, I added pdqsort to the benchmark:

https://github.com/orlp/pdqsort

Here are some of the results on an Ivy Bridge hackintosh:

      size, qsort, inline, sort, stable_sort, pdqsort, radix7

• pottery

  14 119 1.8 C

  Pottery - A container and algorithm template library in C (by ludocode)

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/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

• InfluxDB

  www.influxdata.com sponsored

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

Suggest a related project