Algorithms – Choosing Different Algorithms Based on Input Size

algorithm-analysisalgorithmscomplexityperformance

I recently finished a course on advanced algorithms, and another on complexity & computability theory, and in the past few days my mind has been somewhat preoccupied by this question.

Why don't we just use a different algorithm based on the size of the input?

I'm asking this question because I've never seen this done in practice or heard of it, and I'm also simply curious about the answer. I also tried looking it up on StackExchange and Google with various queries but couldn't come up with anything remotely related to my question.

I'll take the example of sorting algorithms, as they're quite common and there are so many, with different properties and runtime complexities.

Say I have three algorithms, SortA, SortB and SortC. SortA is incredibly efficient on inputs of size <= 100 but becomes very slow on inputs that are any bigger; SortB is more efficient on inputs of length > 100 than SortA but falls off quickly after a size of 1000. Finally, SortC isn't very fast on inputs of size < 1000, but is faster than SortA and SortB on very large inputs.

Why shouldn't/couldn't I make a function like this (written in pseudo-C#-ish code for simplicity)? Or why isn't it done in practice?

int[] Sort(int[] numbers) {
    if (numbers.Length <= 100) {
        return SortA(numbers);
    } 
    else if (numbers.Length <= 1000) {
        return SortB(numbers);
    } 
    else {
        return SortC(numbers);
    }
}

I'm assuming some of the potential reasons are that

it's more code to write,
more potential bugs since there's more code,
it's not necessarily easy to find the exact breakpoints at which some algorithm becomes faster than another, or it might take a lot of time to do so (i.e. running performance tests on various input sizes for every algorithm),
the breakpoints could only be on small or medium-sized input, meaning there won't be a significant performance increase that is worth doing the additional implementation work,
it just isn't worth it in general, and is only used in applications where performance is crucial (similar to how some numerical algorithms use a different method to solve a problem based on the properties of a matrix, like symmetry, tridiagonality,…),
input size isn't the only factor on an algorithm's performance.

I'm familiar with Landau/Big O notation, so feel free to use it in your answers.

Best Answer

Why don't we just use a different algorithm based on the size of the input?

We do. Hybrid algorithms are used all the time.

Why shouldn't/couldn't I make a function like this (written in pseudo-C#-ish code for simplicity)? Or why isn't it done in practice?

That is quite literally how most real-world implementations of sorting algorithms look like.

E.g. quick sort has quite a high overhead, so every real-world quick sort implementation switches to insertion sort for the simple cases at the lower levels of the recursion tree. Instead of switching algorithms at the leaves of the recursion, you can also simply stop sorting altogether at some pre-defined partition size, and then run insertion sort once on the "almost-sorted" result of the "aborted quick sort". This may be more efficient, because instead of having many tiny insertion sorts, you have one longer one, so you don't constantly switch between quick sort and insertion sort in the instruction cache.

Merge sort is also often combined with insertion sort. For example, for cache efficiency, you might want to switch to an in-place insertion sort as soon as the partitions are small enough to fully fit into the cache.

One of the most-widely used sorting algorithms is Timsort, which was implemented for CPython in 2002 by Tim Peters, and has since been adopted by (among others) Oracle JRE (and many others, e.g. IBM J9) as Arrays.sort for reference types, Android, V8, Swift, and GNU Octave. It is a hybrid insertion sort and merge sort, It tries to find "runs" of already sorted elements and merges those; if it can't find any runs, it will create them by partially sorting the list with insertion sort.

Considering that it is used in some of the most widely-used implementations of some of the most widely-used languages, i.e. in Android and Swift (in other words, on pretty much every smartphone and tablet) and also in Java (in other words on pretty much every desktop and a large number of servers) and V8 (i.e. in Chrome and Node.js) and CPython, we can quite confidently say that there is probably not a single person on the planet who has not used it in some form. I don't know about you, but I wouldn't call that "not done in practice", in fact, it doesn't get any more practical than running on almost every computer in the world.

it's not necessarily easy to find the exact breakpoints at which some algorithm becomes faster than another, or it might take a lot of time to do so (i.e. running performance tests on various input sizes for every algorithm)

Introsort solves this by being, as the name implies, introspective. It starts off as a quick sort, but it watches itself while it executes, and when the recursion exceeds a certain depth, it switches to heap sort. Regardless of whether it switches to heap sort in between or stays at quick sort, for very small arrays, it then switches to insertion sort.

Introsort is used in several C and C++ standard library implementations, in .NET, and with Shellsort instead of insertion sort as the final algorithm in Go.

As we have seen above, Timsort has a really clever take on this problem: if the input data doesn't fit its assumptions, it simply makes it fit by partially sorting it first!

Related Solutions

Merge sort versus quick sort performance

If you look at your code for swapping you:

// If current element is lower than pivot
// then swap it with the element at store_index
// and move the store_index to the right.

But, ~50% of the time that string you just swapped needs to be moved back, which is why faster merge sorts work from both ends at the same time.

Next if you check to see if the first and last elements are the same before doing each of the recursive call you avoid wasting time calling a function only to quickly exit it. This happens 10000000 in your final test which does add noticeable amounts of time.

Use,

if (pivot_index -1 > start) quick_sort(lines, start, pivot_index - 1);

if (pivot_index + 1 < end) quick_sort(lines, pivot_index + 1, end);

You still want an outer function to do an initial if (start < end) but that only needs to happen once so that function can just call an unsafe version of your code without that outer comparison.

Also, picking a random pivot tends to avoid N^2 worst case results, but it's probably not a big deal with your random data set.

Finally, the hidden problem is QuickSort is comparing strings in ever smaller buckets that are ever closer together,

(Edit: So, AAAAA, AAAAB, AAAAC, AAAAD then AAAAA, AAAAB. So, strcmp needs to step though a lot of A's before looking the useful parts of the strings.)

but with Merge sort you look at the smallest buckets first while they are vary random. Mergsorts final passes do compare a lot of strings close to each other, but it's less of an issue then. One way to make Quick sorts faster for strings is to compare the first digits of the outer strings and if there the same ignore them when doing the inner comparisons, but you have to be careful that all strings have enough digits that your not skipping past the null terminator.

C++ Sorting Algorithms – Optimal Fixed-Size Sequential Sorting

The problem with finding the optimal algorithm is the word "optimal": A sorting algorithm may be optimal in one case, but it will be suboptimal in at least one other case. The question is, what optimum you are designing it for. Take for instance your algorithm. It is optimal for the sequences:

x < y <= z
x >= y > z

(Aside: This means that you failed to optimize the cases x == y <= z and x >= y == z properly, because they could have been handled by the same code paths. But that's not my point here.)

Yet your algorithm is suboptimal for the other four possible orderings. Now, you can write algorithms like yours, that are optimal for any two of the six possible orderings (taking two comparisons), but they will all require a third comparison in the other four cases.

It is simply not possible to write an algorithm that is optimal for any input order. This is true for any count of objects larger than two. That is, you have to decide, what input orderings to optimize for, and whether you have input orderings which you don't want to optimize for.

To take my point a bit further: Consider the two algorithms quick-sort and insertion-sort. Can you say that either one is absolutely better than the other? No, you can't. Quick-sort will be much faster for random input, but it will simply be pawned by insertion-sort on almost sorted input. Only when you know what kind of input data to expect, you can choose one over the other.

It is a bit like trying to measure location and momentum of a quantum particle. If you know one, you have no idea about the other, and vice versa. You can measure both at the same time, but then both will be inexact. Nature simply does not allow you to know both precisely at the same time. Likewise, when you compare x and y first in your algorithm, you are already breaking the symetry of the problem at hand, making optimal sorting of two thirds of the possible input sequences impossible.

Best Answer

Related Solutions

Merge sort versus quick sort performance

C++ Sorting Algorithms – Optimal Fixed-Size Sequential Sorting

Related Topic