Design a Deliberately Inefficient Sorting Algorithm and Analyze Its Complexity
Company: Mercor
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: easy
Interview Round: Technical Screen
Design a sorting algorithm that is as inefficient as you can make it while still being correct: given a list of n elements, it must return them in sorted order. Explain how it works and analyze its time complexity as precisely as you can.
```hint Search instead of sort
A correct sort only has to output one particular arrangement of its input. Think about an algorithm that makes no attempt to use comparisons to narrow down which arrangement that is.
```
```hint Count both halves of the work
When you analyze it, separate the cost of producing each candidate from the cost of checking it, and ask whether every check really costs the same.
```
### Clarifying Questions
- Must the algorithm finish on every run, or is a randomized algorithm that finishes with probability 1 acceptable?
- Are deliberate do-nothing loops allowed, or must every step be work that could plausibly contribute to sorting?
- Are the elements distinct, and is the question about worst-case, average or expected running time?
### What a Strong Answer Covers
- A concrete algorithm, with an argument that it is correct and always terminates
- A complexity analysis that accounts for both generating and checking candidates, and separates the worst case from the best or average case
- A comparison with familiar sorting algorithms and with the lower bound on the number of comparisons any comparison sort needs
- The difference between a deterministic algorithm's worst case and a randomized algorithm's expected running time
### Follow-up Questions
- Is there a slowest possible sorting algorithm? What rule would make that question well defined?
- Instead of enumerating systematically, shuffle the list at random until it is sorted. What are the expected and the worst-case running times?
- Design a slow sort that still works by recursing on subproblems, and set up and solve its recurrence.
- How does the number of arrangements your algorithm searches relate to the minimum number of comparisons any comparison sort needs?
Overview: An algorithms discussion question that asks for a deliberately inefficient but correct sorting algorithm and a careful analysis of its running time. It tests complexity reasoning about extremely fast-growing costs, worst-case versus expected time, and how such a sort compares with the lower bound for comparison sorting.
Read the full Mercor Software Engineer interview experience this question came from