An Explicit and Efficient $O(n^2)$-Time Algorithm for Sorting Sumsets
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912341893840896 |
|---|---|
| author | Mundhra, S. |
| author_facet | Mundhra, S. |
| contents | We present the first explicit comparison-based algorithm that sorts the sumset $X + Y = \{x_i + y_j,\ \forall 0 \le i, j < n\}$, where $X$ and $Y$ are sorted arrays of real numbers, in optimal $O(n^2)$ time and comparisons. While Fredman (1976) proved the theoretical existence of such an algorithm, a concrete construction has remained open for nearly five decades. Our algorithm exploits the structured monotonicity of the sumset matrix to perform amortized constant-comparisons and insertions, eliminating the $\log(n)$ overhead typical of comparison-based sorting. We prove correctness and optimality in the standard comparison model, extend the method to $k$-fold sumsets with $O(n^k)$ performance, and outline potential support for dynamic updates. Experimental benchmarks show significant speedups over classical algorithms such as MergeSort and QuickSort when applied to sumsets. These results resolve a longstanding open problem in sorting theory and contribute novel techniques for exploiting input structure in algorithm design. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16393 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Explicit and Efficient $O(n^2)$-Time Algorithm for Sorting Sumsets Mundhra, S. Data Structures and Algorithms Discrete Mathematics 68W40 (Primary) 68Q25, 68R05 (Secondary) F.2.2; E.1; G.2.1 We present the first explicit comparison-based algorithm that sorts the sumset $X + Y = \{x_i + y_j,\ \forall 0 \le i, j < n\}$, where $X$ and $Y$ are sorted arrays of real numbers, in optimal $O(n^2)$ time and comparisons. While Fredman (1976) proved the theoretical existence of such an algorithm, a concrete construction has remained open for nearly five decades. Our algorithm exploits the structured monotonicity of the sumset matrix to perform amortized constant-comparisons and insertions, eliminating the $\log(n)$ overhead typical of comparison-based sorting. We prove correctness and optimality in the standard comparison model, extend the method to $k$-fold sumsets with $O(n^k)$ performance, and outline potential support for dynamic updates. Experimental benchmarks show significant speedups over classical algorithms such as MergeSort and QuickSort when applied to sumsets. These results resolve a longstanding open problem in sorting theory and contribute novel techniques for exploiting input structure in algorithm design. |
| title | An Explicit and Efficient $O(n^2)$-Time Algorithm for Sorting Sumsets |
| topic | Data Structures and Algorithms Discrete Mathematics 68W40 (Primary) 68Q25, 68R05 (Secondary) F.2.2; E.1; G.2.1 |
| url | https://arxiv.org/abs/2504.16393 |