Codes, cryptography and algorithms · Maths EE idea · Solid

How many comparisons does sorting need?

A research question to start from

Why does any comparison sort need about n log₂ n comparisons in the worst case, and how close do merge sort and insertion sort come?

A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.

Why it works as a maths EE

A lower bound proof (decision trees) and exact counts for real algorithms.

Mathematics you would need

Counting permutations
Decision trees
Logarithms and Stirling's approximation
Recurrences

Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.

One possible line of attack

Prove the decision-tree lower bound.
Count comparisons for merge sort with a recurrence.
Compare with insertion sort in best, worst and average cases.

Scope and difficulty

Solid. Solid.

Pitfalls

Timing code instead of counting.
Average case asserted.

Where to start reading

Search a library catalogue or a university's open lecture notes for: comparison sort lower bound decision tree proof; merge sort recurrence. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).

Make it your EE

Plan this EEOpens the free EE planner with this question as a starting point. Sharpen the questionSix quick checks for a focused research question. Self-check a draftCheck a section against each criterion, free.