Design Distributed Sorting Around an Explicit Helper Contract

Explain how you would sort data distributed across multiple workers when the environment provides a distributed-computation helper API. Describe the algorithm and the helper capabilities you would verify before implementation. ### Constraints The exact function signature, helper names, data placement, partition sizes, and communication guarantees are unspecified. Do not invent a required API. State whether the result is gathered at one worker or remains globally ordered across output partitions. Any concrete primitive or failure model in your design is an explicit assumption. ### Clarifying Questions - What are the ordering rule, duplicate semantics, and required output placement? - Can workers exchange data directly, broadcast pivots, or perform reductions? - How much data can each worker hold, and can data spill to storage? - Does the environment retry failed work, and can messages or partitions be duplicated? ```hint Distinguish local and global order Sorting each worker's data independently does not establish an order between workers' output partitions. ``` ### What a Strong Answer Covers - A globally correct sorting plan under a stated communication model. - Partitioning, redistribution, local sorting or merging, and treatment of duplicates and skew. - Helper-contract validation, data conservation, resource limits, and failure assumptions. ### Follow-up Questions - Which parts of the distributed framework could also support median or mode computation, and which task-specific steps would differ? - What happens if most input values are equal?