Compare Merge Sort with Factorial and Randomized Inefficient Sorts

Describe a comparison-based sorting algorithm whose worst-case time is better than quadratic, then contrast it with sorting methods whose cost grows faster than quadratic.

Part 1 — An Efficient Sort

Use merge sort to walk through splitting, merging, the base case, time complexity, and extra memory. Cover stability and how an adaptive merge-based implementation can take advantage of order already present.

What This Part Should Cover

A valid merge invariant, the reasoning behind $O(n \log n)$, and a clear distinction between an algorithm and a particular runtime's implementation decisions.

Part 2 — Inefficient Sorts

Examine enumerating permutations to find a sorted order and repeatedly shuffling until the input happens to be sorted. Separate finite worst-case bounds from expected time, and evaluate whether a meaningful absolute worst sorting algorithm exists.

What This Part Should Cover

Factorial growth, the assumptions underlying random-shuffle analysis, and why arbitrary extra work rules out a single worst algorithm.

Constraints

For the permutation and random-shuffle discussion, assume $n$ distinct comparable elements, constant-cost comparisons, and independent uniform shuffles whenever randomness is involved. Do not generalize one JavaScript engine's sorting implementation to every virtual machine.

Clarifying Questions

• Are we comparing worst-case time, expected time, memory, or real-world runtime?
• Does the output need to be stable or produced in place?

Hint — Keep the cost of a single attempt separate from the number of attempts: A shuffle-based procedure must both generate a candidate order and check whether that order is sorted.

What a Strong Answer Covers

• Correct merge-sort mechanics and complexity.
• Factorial enumeration and randomized stopping-time analysis.
• Qualified claims about runtime implementations, with no unsupported absolute worst-case label.

Follow-up Questions

• Why should equal elements be taken from the left run first to keep a merge stable?
• How does the shuffle probability change when some values are duplicates?

Overview: Explain merge sort, adaptive merging, permutation sorting, and random-shuffle sorting, while distinguishing expected complexity from worst-case guarantees.