Cloud Sort: An Overhead Caller-Buffer Merge Paradigm with Zero Dynamic Allocations, 25% Bus Write Reduction, and Strict In-Situ Stability

Textbook formulations of standard merge sort allocate an auxiliary array of size N and execute a four-phase merge routine (copying both sub-arrays, comparing, draining both partitions, and copying the merged sequence back). This paper presents Cloud Sort, an asymmetric merge paradigm that achieves O(N log N) time complexity and strict sorting stability using a single caller-allocated floating buffer (the overhead cloud) bounded strictly to ⌈N/2⌉ elements. By lifting only the active left slice (A[l..m]) to the overhead buffer, the ground array's writing slots are vacated in-situ, completely eliminating the ground sub-array copy, the right-partition drain loop, and the final back-copy stage. As a direct consequence of the Zero-Move Right Tail Property, Cloud Sort eliminates 25.0% of physical SRAM data writes (1.5 N log₂ N vs. 2.0 N log₂ N) without internal dynamic memory allocation (malloc/free). We provide a rigorous induction proof of read-before-write memory safety (L_t ≤ R_t), evaluate algorithmic stability across 10,000 differential pseudo-random trials against production TimSort, and benchmark embedded microcontroller execution on the ATmega328P architecture (Arduino Uno). Empirical results confirm that Cloud Sort increases out-of-memory survival thresholds by 14.3%–22.9% and decreases bus write energy dissipation on resource-constrained embedded systems by one-fourth.