Shelfsort: a fast stable sorting algorithm in sqrt(n) memory

• shelfsort

  2 18 3.4 C++

  a stable sort using sqrt(n) memory

• stable-inplace-sorting-algorithms

  1 12 3.7 C++

  new stable in-place sorting algorithms

• InfluxDB

  www.influxdata.com featured

  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.

  

• compiler-explorer

  191 15,198 9.9 TypeScript

  Run compilers interactively from your web browser and interact with the assembly

  

Very interesting, your optimisation may make sense. I played around with the code on https://godbolt.org/ (I added the missing #include ).

• GrailSort

  1 183 0.0 C

  Stable In-place sorting in O(n*log(n)) worst time

I read a bunch of papers on stable in-place merges at the time and yeah you're right that there's normally a fairly significant hidden constant factor preventing them from being practical, but at least two of the papers did result in practical sorts – this one by Pok-Son Kim and Arne Kutzner which led to WikiSort, and another by Huang and Langston for GrailSort. They're competitive with C++'s stable_sort!

Suggest a related project