Katkat
Back

Design the Worst Correct Sorting Algorithm and Analyze Its Complexity

MercorSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Asks you to propose the worst sorting algorithm that is still correct, explain how it works, argue that it always terminates with sorted output, and analyze its best-case and worst-case time and space. It tests counting arrangements, reasoning about factorial growth and stating what makes such a question well defined.

Sorting algorithms are usually compared by how fast they are. Turn the question around: what is the worst sorting algorithm you can come up with? It must still be correct, meaning it always terminates and returns the input in non-decreasing order, but it should be as inefficient as you can reasonably justify.

Explain how your algorithm works, argue that it is correct, and analyze its time and space complexity.

Constraints and Clarifications

  • The input is a list of n values with a total order. Duplicates are allowed.
  • The algorithm must always terminate with a correct result.

Clarifying Questions

  • Must the algorithm be deterministic, or is a randomized algorithm that terminates with probability 1 acceptable?
  • Does deliberately wasted work, such as sleeping or empty loops, count as "worse", or must every step contribute to finding the sorted order?
  • Should the analysis cover the worst case, the average case, or both?

Hints

Hint 1

Start from the definition: A sorted output is one particular arrangement of the input values, and checking whether a given arrangement is sorted is easy. Ask how little cleverness an algorithm needs while still being guaranteed to find that arrangement.

Hint 2

Count two things separately: For the analysis, count how many candidates your algorithm may examine and what it costs to produce and check each one, then combine the two.

Follow-up questions

  • How would you produce the candidates one at a time without storing them all, and what does that cost per candidate?
  • Compare your algorithm with one that shuffles the list randomly until it is sorted. Which has the better expected running time, and which has a bounded worst case?
  • Can a sorting algorithm always be made worse? What rule would make "the worst sorting algorithm" a well-defined question?
  • Roughly how large can `n` be before your algorithm becomes infeasible on a modern machine?