Overview

“I do not know how to design efficient algorithms, but I do know how to recognize them.”

Many software developers feel this way. We learn to write step-by-step instructions for tasks like computing interest or registering payments—business processes that directly map to code—but when asked to solve a problem efficiently e.g., sorting a list, we realize our methods often remain naive. We can’t easily go from a correct but slow solution to an optimized one, because textbooks and interview practices usually present optimized algorithms “fully formed.” This essay aims to fill that gap by starting with the simplest and slowest solution—permutation sort—and incrementally refining it until we arrive at mergesort. By witnessing how an optimized algorithm emerges, we develop true problem-solving skills, rather than memorizing final formulas.

Sorting is just one illustration of how naive-but-correct algorithms can be refined into efficient solutions. The iterative approach below—beginning with permutation sort, gradually limiting factorial blow-up, merging at each step—reveals how mergesort’s elegant structure emerges naturally from small, logical improvements on a brute-force baseline. This same process applies across problem-solving domains. Seeing the path from worst to best not only cements your understanding of how sorting works but also trains you to tackle any problem by:

1. Capturing it clearly,
2. Stating a naive solution even if factorial or exponential,
3. Finding ways to prune or restructure the search space,
4. Iterating until you reach a solution that’s both correct and efficient.

In a world of “Leet coding” interviews, I think recognizing the below journey makes you a true problem solver, not just someone who can reproduce a memorized algorithm. You’ll be prepared to invent or improve solutions for problems that go beyond the standard library—precisely the skill set that leads to real innovation in software engineering.

Capturing the Problem of Sorting

To understand sorting, it helps to formalize it: 1. We have a list of elements, each of which can be compared with another to decide if it is less than, equal to, or greater than another. 2. We say is sorted in ascending order if, for every element in , . 3. If any element is larger than , the list is not sorted. The goal is: given an unsorted list, produce a new list or modify the same list so that it is sorted in ascending order. —

The Naive Starting Point: Permutation Sort

How It Works

1. Generate all permutations of your list of elements. That’s permutations.

2. Check each permutation to see if it’s sorted.

3. Return the first sorted permutation you find or pick any sorted one.

Complexity

There are permutations; each one requires time to check if it’s sorted.

Overall complexity: , which quickly becomes intractable for or so. Despite being terribly inefficient, it provides the ultimate baseline: it is obviously correct, and it clarifies the enormity of the sorting search space. If nothing else, this method ensures we understand exactly what the problem entails.

Permuting elements yields permutations.
But permuting elements yields —still factorial, but less explosive than .

Hence:

1. Divide your list of size into two halves of size .
2. Permutation sort each half now you’re generating permutations twice.
3. Merge the two sorted halves. Merging takes time.

Why it’s better: is much smaller than for larger . For instance, , while . Doing permutations is far less than . In big-O notation it’s still factorial, but it’s an example of a divide-and-conquer improvement over enumerating all permutations of the entire list at once.

Extending the idea: Recursively Divide & Permute Smaller Sub-Lists Why stop at one division?

We can recursively keep dividing each sub-list until it reaches some small size . Then:

1. If the sub-list size , use permutation sort it’s affordable if is small.

2. Otherwise, keep dividing in half.

3. Merge the sub-lists once they’re individually “sorted.”

Complexity Discussion

If you pick , each half is still large, so you’ll face . - If is a fixed constant like 2, 3, or 4, then enumerating permutations in a sub-list of size takes operations—still technically factorial, but bounded by a small constant.
Once each sub-list of size is sorted, merging them follows a structure similar to mergesort—linear merges per sub-list, and levels of merging. The total cost of merging is .

Hence, if you fix , enumerating “all permutations” of a 2-element list is effectively just “check and swap if out of order.” This is . All the rest of the work is in merging sorted sub-lists, level by level, which is how mergesort arrives at .

Realizing This Is Basically Mergesort

Mergesort is normally introduced as:

1. If the list has size 1, it’s sorted trivial.

2. Otherwise, split into halves, recursively sort each half, then merge.

But you can also see mergesort as:

1. Keep dividing until you have sub-lists of size 2 or 1.

2. “Permutation sort” each 2-element sub-list only 2 permutations to consider.

3. Merge your way up. Both descriptions produce complexity.

The difference is pedagogical: typical textbooks skip the “permutation enumeration” angle because it’s usually regarded as an impractical approach for sub-lists beyond a tiny size. Yet, from a teaching perspective, this path from “full factorial” to “factorial only on very small sub-lists” to “pure merges” is (at least to me) enlightening.

Designing Efficient Algorithmic Solutions From the Worst Logical Sort to Mergesort