The Flash Adaptive Sort was published at SAC 2021 (paper).
The adaptive sort either uses external merge sort or index-based minsort to sort data depending on the data distribution and flash performance (read vs write times). It can be used for embedded devices with low memory.
The adaptive sort has the following benefits:
- Minimum memory usage is only two page buffers. The memory usage is less than 1.5 KB for 512 byte pages.
- No use of dynamic memory (i.e. malloc()).
- Easy to use and include in existing projects.
- Open source license. Free to use for commerical and open source projects.
- adaptive_sort.c, adaptive_sort.h - implementation for adaptive sort
- flash_minsort.c, flash_minsort.h - implementation of index-based minimum value sort
- flash_minsort_sublist.c, flash_minsort_sublist.h - sorted sublist variant of minimum value sort