Proximity Partition Sort (JiajunSort)

A Novel Divide-and-Conquer Sorting Algorithm

Abstract

We present Proximity Partition Sort (PPS), also known as JiajunSort, a novel divide-and-conquer sorting algorithm that partitions elements based on their proximity to minimum and maximum values rather than using traditional pivot-based approaches. The algorithm demonstrates competitive performance with O(n log n) average-case complexity while maintaining robustness against worst-case scenarios through hybrid optimization techniques. We provide both recursive and iterative implementations, along with a highly optimized C version that incorporates fallback mechanisms for degenerate cases. Experimental results show that PPS performs competitively with established algorithms while offering unique advantages in specific data distributions.