I was reviewing sorting algorithms these days, and came up a new one which i have not seen on any paper before:

1. split input data into S=logn blocks, each block size T= n/logn (expect the last one)

2. create min-heap on each block1 .. blockS

3. for each element in block0:

if it is bigger, swap it with smallest element in heapsheapify the modified heap4. now block0 conains max n/logn elements of input

5. recursively sort block0

6. process block1..blockS in the same way as (3,4,5)

i have write an implementation on https://github.com/richox/sorting_al...tiheap_sort.hh

it's slower than the original heap sort, but a bit faster than dijkstra's smooth sort.