## Prompt Compare common sorting algorithms and choose an implementation for each workload below: 1. A large in-memory array of primitive keys that needs predictable worst-case latency. 2. A linked list that must be sorted stably. 3. A stream of records too large to fit in memory. 4. A nearly sorted array in a user interface where simplicity and low overhead matter. Explain time and space complexity, stability, adaptiveness, cache behavior, and failure modes. A name alone is not an answer; connect each choice to the data representation and constraint. ### Constraints & Assumptions - Comparison sorting is the baseline unless a bounded key domain is explicitly used. - “Stable” means equal keys retain their original relative order. - Memory overhead and worst-case behavior matter independently of average complexity. - External data is available through sequential reads and writes. ### Clarifying Questions to Ask - Must sorting be in place, stable, deterministic, or parallel? - What is the key distribution and is the domain bounded? - Does the data fit in memory, and what storage access is cheap? - Is adversarial input possible? ```hint Organize by properties, not memorized names For every candidate, state worst and average time, extra space, stability, and which input patterns improve or degrade it. ``` ### What a Strong Answer Covers - A defensible comparison among insertion sort, merge sort, heap sort, quicksort or introsort, and non-comparison options where applicable. - Why linked lists and arrays favor different merge and partition operations. - How introspection avoids quicksort's quadratic worst case. - Run generation and multiway merge for external sorting. - Why nearly sorted data can favor an adaptive algorithm despite the same worst-case class. - Numeric, memory, and implementation trade-offs rather than claiming one universal best sort. ### Follow-up Questions 1. How does stable sorting affect a sequence of sorts by different keys? 2. Why can an `O(n log n)` algorithm lose to another with the same bound? 3. When is counting sort inappropriate despite linear asymptotic time? 4. How would parallelism change the external merge design?