# How to design a faster sort algorithm? Is there sort of meta-algoritm for it? Or we do not understand how better sort algorithms were discovered?

I know that Quicksort or MergeSort are faster than, say, Bubblesort or Selection sort. And I know why (complexity metrics) but I never been able to find out how could someone start with, for example Bubblesort, and then optimize parts of the code to end up with Quicksort or MergeSort… Is it even possible?

Or it’s the case that going from Bubblesort to Quicksort such a large conceptual leap that there isn’t really a way to “meta-explain” what is the thinking process to go from one to the other?

Another way to put this is: Is there an meta-algorithm to make an algorithm like Bubblesort become an algorithm like Quicksort? Or this still understood so poorly that all we can say is: give the problem to a planet full of human neural networks and wait some years?

I wonder if the way to find out would be to start with the slowest possible algorithm: reorder the list in all possible arrangements, select the one that is ordered and from there look for ways to add constraints to be more efficient… perhaps using something like miniKanren relational programming…

• I don't think Quicksort or Mergesort were necessarily found as an improvement of another sorting algorithm… Also your question is very vague, I don't think anyone can answer it as is. Sep 18 at 19:52
• For the anecdote, in the early days, Metzner tried to improve on BubbleSort by using larger and larger strides during the sorting passes. This lead to ShellSort, a now obsolete algorithm. Sep 19 at 9:54

Algorithm design is known to be an art. There is no magical recipe. It all depends on the mathematical properties of the problems addressed.

In the case of sorting, the designers were helped by a few theoretical considerations:

• there are $$n!$$ ways to permute an array, so any sort that relies on comparisons (each time one bit of information) must perform at least $$\lg(n!)\sim n\lg(n)$$ comparisons. So there is no point searching for faster algorithms.

• finding the rank (sorted position) of every element allows you to identify the permutation; this can be done by comparing every element to every other, which takes $$\sim n^2$$ comparisons.

• among the $$n^2$$ comparisons, many are redundant due to the transitivity property ($$a). This gives hope for $$o(n^2)$$ solutions.

These a priori complexity results serve as guides for algorithm design and tell you how close you are from a good solution.

Now two general techniques can be tried:

• incremental processing: assuming you sorted the $$m$$ first elements, what does it take to sort the $$m+1$$ first elements ? (insert the new element at the right place $$\to$$ StraightInsertionSort); or assuming you sorted the $$m$$ smallest elements, which comes next ? (take the smallest of the remaining elements $$\to$$ StraightSelectionSort).

• divide & conquer: assuming you can sort independently the first halve and second halve of the array, what does it take to obtain the fully sorted array ? (perform a merge operation $$\to$$ MergeSort); or, assuming that you can presort the array in such a way that the first elements are smaller than the last elements, what does it take to get the fully sorted array ? (the first operation is called a partition; after the partition, it suffices to concatene the sorted subsequences).

It turns out that incremental processing yields simple but $$O(n^2)$$ algorithms, while D&C results in $$O(n\log(n))$$ for MergeSort (but requires an extra array), and $$\Omega(n\log(n))/O(n^2)$$ for Quicksort (so is not optimal, but fast in practice anyway).

None of these algorithms are perfect. There is another, which does not fall in the above categories and relies on an unexpected concept: the heap. This is a special data structure which consists in an implicit binary tree with an order relation between the keys. And it turns out that building a heap takes $$O(n)$$ time, and extracting the smallest element $$\lg(n)$$ time at worst. This gives birth to HeapSort, a good algorithm with guaranteed $$O(n\lg(n))$$ behavior.

There is much more to say about sorting and algorithm design. The morale is that there are general principles, but creativity is still required.

• Nice answer. Are there any book you recommend on this art? All algorithm books I can find look more like recipe lists: here’s is how to do Quicksort, and these are its performance characteristics, but I have yet to find a book that is more like: here is what sorting conceptually is, here is how you mathematically analyze it, and here is what the performance boundaries of what an algorithm can do with it are Sep 18 at 22:13
• @Luxspes Robert Sedgewick is one of the mondial references on sorting. You may find answers in his book Algorithms. Sep 18 at 22:35
• "Horowitz and Sahani, Fundamentals of Computer Algorithms": that's a pretty old book, but in the old days, books were better. :-) Sep 19 at 6:44
• @YvesDaoust Your answer is very helpful and inspiring, I have a question why runtime of Quicksort is $\Omega(n\log(n)/O(n^2)))$, I only know the expected runtime is $n\log(n)$ when the pivot is selected randomly.
– Jxb
Sep 22 at 7:28
• @Jxb: the best case takes $\Theta(n\log n)$ comparisons (when all partitions are perfectly balanced), and the worst case $\Theta(n^2)$ (when all partitions are maximally imbalanced). Sep 22 at 7:32

No matter how much one optimizes its code, a bad algorithm will always be bad. The key to great software is starting with a great algorithm.

What distinguishes an algorithm is something that makes it fundamentally different from other algorithms. Iteratively improving an algorithm will never result in something that is fundamentally different.

Consider an extreme example.
The best theoretically possible algorithm will require n×log(n) comparisons. But if the comparison keys are dense enough (or if they can hash to numbers that are dense enough), they can be sorted with a linear order algorithm (radix sort), which is significantly better than n×log(n).
There is no way anyone can start with a comparison sort and gradually improve it into a radix sort; the two algorithms are so fundamentally different.

• (According to en.wikipedia, radix sort was somewhat common in 1923.) Sep 19 at 7:38
• @greybeard, radix sort is how most people would sort a deck of cards. Radix sort was used as far back as the 1800s for sensus queries, as it sort could be implemented in mechanical hardware. I expect it was the first method of computer sorting. I can even remember seeing them used into the early 1970s to sort punched cards. Many movies from the 1970s and even 1980 used mechanical sorters (and spinning tape drives) to represent computers doing calculations. See Punched card sorter - Wikipedia. Sep 19 at 14:28

Bubblesort to Quicksort requires some cleverness, but is a quite natural progression.

First, you implement Bubblesort, and you find that for 100,000 random items it is indeed very slow. 100,000^2 operations. You'll find easily that if you split the array into two groups of 50,000, sort both and merge the results, you only need 50,000^2 * 2 + 100,000 or so operations which is almost twice as fast. And then obviously you sort a 50,000 item array by splitting it into two parts of 25,000. And if you follow this down and measure, you'll find that for some rather small n the bubble sort is actually faster. Now we've got merge sort.

Mergesort is actually already optimal in Big-O notation, but making an algorithm twice or three times as fast is still worthwhile. So we would analyse what's bad about merge sort, and it is mostly the fact that we need additional memory. Swapping elements doesn't require more than constant additional memory. Figuring out the Quicksort partition algorithm is difficult, but possible enough.

When you examine Quicksort more closely, two annoying things are the worst case which you fix by randomising the pivot, and the fact that it doesn't take advantage if the data is already sorted or mostly sorted.

Some implementations now check how many initial elements are in either ascending or descending order, and how many elements at the end are in either ascending or descending order. And if the numbers are significantly high compared to the total number of items (say large compared to n / log n) we can sort the unsorted items and then do one or two merges. This will be linear if we combine two sorted arrays, or if we take a sorted array with just one change, or a sorted array with O (n / log n) items appended, and usually be an improvement if we take a sorted array with two or three changes. (And the check is very fast if it doesn't gain anything).

Another implementation assumes that your array was created by starting with a sorted array, and adding / removing / appending / changing a few values, fewer than O (n / log n). Here we can remove all the items that are not in sorted order, sort them separately, then merge. This also works well if you take an array containing a million names, sorted correctly according to one of the official German sorting orders, and sorting it according to the official Swedish sorting order.

The last two changes are both quite natural.

I agree that there is no recipe and others provided insight on how matters evolved or can evolve. A key aspect hindering the design of your "meta-algorithm" is a lack of "modularity" in Computer Science. The theory of algorithm design (and analysis) is not on par with say civil engineering, for which automation is more advanced. Newton's calculus supports the prediction of properties of a bridge from the blue-prints. Hence such projects can be designed and analysed in a modular fashion (properties of the materials lead to a prediction of properties of the end product).

In CS, design and analysis techniques are tailored to particular algorithms/problems as opposed to being based on a single foundational theory. In many cases there are infinitely many inputs, each of which could change the execution behaviour in a different way. Modularity is not guaranteed (i.e. the design and analysis of parts of the code does not guarantee control/predictability of the design and analysis of the whole).

Computer science faces a hurdle on that front since all parts interact in a multitude of ways (input-dependency) and is not yet at the stage where your question can be fully answered. The field is less than 100 years old (as a science). Other fields, in comparison, have been developed for millennia (though of course computation has been around for a lot longer than the advent of computers).

The other answers here explain very well the mathematical idea and thought process to come up with a sorting algorithm, there might be cases where even the "most optimal" algorithm you have, may not deliver the performance you expect. Of course they all sort so they are correct, but in practical scenarios, lower execution times(time and space complexities)are desirable. Often, algorithms are "combined" resulting in a hybrid implementation, which performs better than any algorithm alone. The choice of algorithms to pick depends on the nature of data and empirical results.

An example: Combining merge sort and insertion sort is helpful as for fewer values and completely/nearly sorted data, insertion sort performs better than merge sort. So you can perform merge sort, and once the sub problem size becomes reasonably small, you can use insertion sort.

Notable examples implementing these ideas are Timsort and Introsort.

• Designing a "perfect" general-purpose sorting algorithm is an endless quest, if not hopeless. For critical applications, it can be worthwhile to use ad-hoc algorithms to exploit the particular characteristics of the data. Sep 20 at 7:11

And here is my meta-algorithm for creating fast algorithms and fast implementations of algorithms:

Step 1: Create a working algorithm.

Step 2: Run the algorithm and figure out what bits run slower than you think they should. At this point you also understand the problem better.

Step 3: With your better understanding of the problem, and your knowledge what makes your current algorithm slower than it should be, create a new algorithm and go back to Step 3.

You stop when you think your benefits from a faster algorithm don't outweigh the cost of creating a faster algorithm anymore. You may continue if you find common situations that you might be able to solve much faster than the general case. It's pointless to optimise for the worst case if the worst case never happens for problems that people actually try to solve.

• I don't think that this works. Well, in fact it works, but takes an army of algorithmicians working for decades. By the way, algorithms are not comparable, as their performance is not a function of $n$, but a whole statistical distribution of running times, highly dependent on the data set. Also, they often don't enjoy the same properties: one can be in-place, another adaptive, a third with guaranteed $O(n\log n)$ behavior, a fourth not relying on comparisons, a fifth cache-friendly... Sep 20 at 7:13
• Yves, works well enough for me. Rule of thumb is that the first implementation can be improved by a factor 10 - if it’s worth the effort. Some can be improved a lot more. And I’m not talking about decades of effort. Sep 20 at 17:30
• Strangely I have yet to see an algorithm book that teaches this, they are all like traditional recipe books treating each recipe as an independent thing Sep 22 at 13:42
• Do you know of a book that presents problem requirements that lead to satisfaction with least efficient algorithms and then incrementally alters problem requirements, profiles algorithms under new situations, identify hot spots and then guiding the reader from, for example, bubble sort to shell sort to quick sort and then to heap sort? Sep 22 at 13:46
• @Luxspes The book you want is "Introduction to the Design & Analysis of Algorithms" by Anany Levitin. It's dry, dense, and has a lot of math in it, but it's considered a great introduction to algorithm design. Sep 30 at 0:40

I'm going to pull my answer from the book Introduction to the Design and Analysis of Algorithms by Anany Levitin. Anything in blockquotes is directly from the book. Here's the steps he gives in the book:

1. Understanding the Problem

Read the problem’s description carefully and ask questions if you have any doubts about the problem, do a few small examples by hand, think about special cases, and ask questions again if needed.

2. Choosing between Exact and Approximate Problem Solving

The next principal decision is to choose between solving the problem exactly or solving it approximately. In the former case, an algorithm is called an exact algorithm; in the latter case, an algorithm is called an approximation algorithm. Why would one opt for an approximation algorithm? First, there are important problems that simply cannot be solved exactly for most of their instances; examples include extracting square roots, solving nonlinear equations, and evaluating definite integrals. Second, available algorithms for solving a problem exactly can be unacceptably slow because of the problem’s intrinsic complexity. This happens, in particular, for many problems involving a very large number of choices...

3. Design an algorithm

Describe the algorithm, usually using pseudocode.

4. Proving an Algorithm's Correctness

Once an algorithm has been speciﬁed, you have to prove its correctness. That is, you have to prove that the algorithm yields a required result for every legitimate input in a ﬁnite amount of time. For example, the correctness of Euclid’s algorithm for computing the greatest common divisor stems from the correctness of the equality gcd(m, n) = gcd(n, m mod n)

5. Analyze the Algorithm

Measure how well the algorithm performs. There are several qualities to keep in mind:

• Time efficiency (how fast the algorithm runs)
• Space efficiency (how much extra memory it uses)
• Simplicity (how simple it is; simple algorithms tend to have less errors)
• Generality (how general the algorithm is and the set of inputs it accepts)

If you are not satisﬁed with the algorithm’s efﬁciency, simplicity, or generality, you must return to the drawing board and redesign the algorithm. In fact, even if your evaluation is positive, it is still worth searching for other algorithmic solutions.

6. Code the algorithm

Finally code the algorithm. Make sure to test to make sure it's working properly.

"Okay this is fine and dandy, but that still doesn't answer the question about how we got from Bubble Sort to something like Quicksort"

It's a fact that an array grows, the time to sort doesn't grow linearly, but exponentially. What we realized was that partitioning the array into smaller sub-arrays, sorting those sub-arrays, then recombining them resulted in a massive speedup. This is basically what algorithms like Merge Sort and Quicksort is doing.

• Make sure to test to make sure it's working properly Nah, the algorithm works: 1) otherwise it wouldn't be an abstract solution to the problem 2) you've proven it in 4.. Test your implementation to work acceptably… Sep 30 at 5:45
• @greybeard Sometimes you screw up the coding portion. That's why it's important to test what you coded. For example, even though Quicksort is extremely common and well documented, people still often code it incorrectly on their first try. Also, you could run into hardware limitations that you didn't consider before. Sep 30 at 19:05