## Compare Quicksort and Mergesort in Practice Compare Quicksort and Mergesort as choices for sorting a large collection. Explain their mechanics, complexity, memory use, stability, failure modes, and the input or platform characteristics that influence the choice. Include how you would implement and test each algorithm rather than reciting average-case complexity alone. ### Constraints & Assumptions - Consider arrays in memory as the default, then discuss linked structures or external data where the trade-off changes. - Distinguish guarantees from expected behavior. - Address duplicate-heavy, already sorted, reverse-sorted, and adversarial inputs. ### Clarifying Questions to Ask - Is stable ordering required for equal keys? - Is worst-case latency more important than average throughput? - Must the sort be in place, and can the data fit in memory? ### Part 1 — Analyze Quicksort Explain partitioning, pivot selection, recursion depth, and the conditions behind expected `O(n log n)` versus worst-case `O(n^2)` time. Discuss duplicate handling and practical mitigations. ```hint Stress the partition Trace one partition when all keys are equal and another when the pivot is repeatedly an extreme value. ``` #### What This Part Should Cover - A clear partition invariant and correct treatment of the pivot. - Randomized or robust pivot selection and three-way partitioning for duplicates. - Expected time, worst-case time, stack use, cache locality, and typical instability. - Recursion-depth controls or an introspective fallback. ### Part 2 — Analyze Mergesort Explain divide, merge, and buffer management. Compare array and linked-list implementations and discuss why Mergesort is useful for stable or external sorting. ```hint Account for data movement Separate comparison count from allocation, copying, sequential access, and the cost of merging data that does not fit in memory. ``` #### What This Part Should Cover - The merge invariant and stable tie handling. - Guaranteed `O(n log n)` time and auxiliary-space requirements for arrays. - Natural fit for linked lists, sequential I/O, and external merge passes. - Reuse of buffers and tests for boundaries, duplicates, and stability. ### What a Strong Answer Covers - Correct mechanics and complexity claims for both algorithms. - A decision tied to stability, memory, worst-case guarantees, locality, and data layout. - Concrete implementation risks and tests rather than one algorithm being declared universally superior. ### Follow-up Questions - Why can Quicksort outperform Mergesort on an in-memory array despite weaker worst-case guarantees? - How would you sort data larger than available memory? - What input exposes a two-way Quicksort partition that handles duplicates poorly?