How to Sort in a Refrigerator: Simple Entropy-Sensitive Strictly In-Place Sorting Algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912946250055680 |
|---|---|
| author | Gila, Ofek Goodrich, Michael T. Sridhar, Vinesh |
| author_facet | Gila, Ofek Goodrich, Michael T. Sridhar, Vinesh |
| contents | While modern general-purpose computing systems have ample amounts of memory, it is still the case that embedded computer systems, such as in a refrigerator, are memory limited; hence, such embedded systems motivate the need for strictly in-place algorithms, which use only O(1) additional memory besides that used for the input. In this paper, we provide the first comparison-based sorting algorithms that are strictly in-place and have a running time that is optimal in terms of the run-based entropy, H(A), of an input array, A, of size n. In particular, we describe two remarkably simple paradigms for implementing stack-based natural mergesort algorithms to be strictly in-place in O(n(1 + H(A))) time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_05676 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | How to Sort in a Refrigerator: Simple Entropy-Sensitive Strictly In-Place Sorting Algorithms Gila, Ofek Goodrich, Michael T. Sridhar, Vinesh Data Structures and Algorithms While modern general-purpose computing systems have ample amounts of memory, it is still the case that embedded computer systems, such as in a refrigerator, are memory limited; hence, such embedded systems motivate the need for strictly in-place algorithms, which use only O(1) additional memory besides that used for the input. In this paper, we provide the first comparison-based sorting algorithms that are strictly in-place and have a running time that is optimal in terms of the run-based entropy, H(A), of an input array, A, of size n. In particular, we describe two remarkably simple paradigms for implementing stack-based natural mergesort algorithms to be strictly in-place in O(n(1 + H(A))) time. |
| title | How to Sort in a Refrigerator: Simple Entropy-Sensitive Strictly In-Place Sorting Algorithms |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.05676 |