Page Merge Sort

Stable, O(nlog(n)) time, O(sqrt(n)) additional memory.

It is a sorting algorithm based on the approach of merging algorithm described here: https://max-arbuzov.blogspot.com/2021/10/merge-sort-with-osqrtn-auxiliary-memory_22.html

The previuosly described algorithm has two stages:

Stage 1 – so called pre-merging;

Stage 2 – reordering pages.

Stage 2 is performed each time the sub-arrays are merged. And it is not necessary for the entire sort run – just one-time pages reordering will be enough. It will require some modifications to the algorithm.

The new sorting algorithm will approximately be:

1. Split unsorted array into pages.

2. Sort elements in each page.

3. Merge pages until there will be single range of pages. It can be done recursively or not.

4. Rearrange (reorder) pages.

This sorting algorithm requires less element moves compared to sorting algorithm based on the previous algorithm under the link.