# Compare Sorting Algorithms and Brute-Force Permutation Sort Compare several common sorting algorithms, then analyze a deliberately inefficient strategy that generates every permutation, tests whether each permutation is sorted, and returns a sorted one. Derive its time and space complexity and explain why the nested work is worse than ordinary comparison sorting. ### Constraints & Assumptions - The input contains `n` comparable values and may include duplicates. - Discuss best, average, and worst cases where they materially differ. - Address stability, in-place behavior, and data-shape sensitivity. - For permutation sort, first analyze distinct values, then explain what duplicates change. ### Clarifying Questions to Ask - Is worst-case runtime or practical average performance most important? - Must equal elements retain input order? - Is auxiliary memory constrained? - Can keys be exploited by a non-comparison algorithm? ```hint Count candidates and validation work separately There are factorially many candidate orders, and checking one candidate for sortedness costs linear time in the worst case. ``` ### What a Strong Answer Covers - Correct complexity and properties for representative algorithms - The comparison-sort lower bound and when it does not apply - A derivation of factorial permutation-sort cost rather than a memorized label - Effects of duplicates, early stopping, materialization, and recursion depth ### Follow-up Questions 1. Why can counting sort beat `O(n log n)` without contradicting the comparison lower bound? 2. How does generating permutations lazily change peak space but not worst-case time? 3. Which sorting algorithm would you choose for nearly sorted data with a stability requirement?