Splits the array into fixed-size blocks (block size chosen as a power-of-two based on element type size), maintains an index array over block groups, and merges groups by manipulating that index together with a circular scratch buffer. A final RearrangeWithIndex pass physically permutes the blocks according to the merged index. When a block group is large enough, IsSortedForward and IsSortedBackward scan for pre-sorted prefixes or suffixes and recurse only on the unsorted middle.
A re-implementation of Boost.Sort's flat_stable_sort. Uses only O(n/b) block indices plus O(b) circular scratch (where b is the block size, a type-dependent power-of-two), keeping auxiliary space well below O(n) while guaranteeing stability and O(n log n) worst-case time. Achieves O(n) on sorted or reverse-sorted input.