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?

Question

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…

Answer 1

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<b\land b<c$$\implies a<c$). 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.

Answer 2

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.

Answer 3

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.

Answer 4

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).

Answer 5

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.

Answer 6

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.

Answer 7

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 specified, 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 finite 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 satisfied with the algorithm’s efficiency, 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.