Asymmetric External Memory (AEM) model, introduced by Blelloch et al. at SPAA 2015, models computations when the data is stored on new non-volatile memory (NVM) storage, rather than tradition DRAM memory. The significant difference in NVMs is the fact that the cost of writing data is significantly higher than the cost of reading it. This asymmetry requires new algorithmic techniques, which allow the trade-off of write accesses for extra read accesses during computation.
In this talk I will present sorting algorithms, which achieve such a trade-off between read and write accesses in the AEM model. If time permits, I will also show a lower bound that proves that this trade-off is asymptotically optimal.