- Blackout
- Faster Than Light
- Hex Board
- Invariants
- Listening To OEIS
- Logic Gates
- Penrose Maze
- Syntactic Sugar
- Terminal Colors

*Linear search is faster than binary search for integer arrays with less than
150 elements.*

In an algorithms class, you learn that merge sort has running time
O(N*logN) while insertion sort has running time O(N²). This
implies that *in the limit*, as the size of the list you’re sorting gets
arbitrarily large, merge sort will be faster than insertion sort. (And
furthermore, it will win out by an arbitrarily large amount if the list gets
large enough.)

But it doesn’t say anything about which algorithm is faster for *small* lists.
In fact, insertion sort is faster than merge sort for small lists in practice.
As a result, *serious* sorting algorithms like Timsort use an
asymptotically-fast sort like merge sort for large lists, but fall back to
insertion sort for lists with fewer than 64 elements or so.

What about *searching* a sorted list? Binary search is O(logN)
while linear search is O(N). But linear search is faster for
smaller lists because it has less overhead and causes fewer branch
mispredictions. So how large does your list have to be for linear search to be
faster?

The last time I searched for this, I came up fairly empty handed, so I
benchmarked it myself. But apparently I was bad at searching, so here is
a blog post very similar to this one that comes to a similar conclusion.
Alternatively, if you want to see a benchmark of *very fast* vectorized binary
searching, look here.

To benchmark this, I wrote totally naive Rust code for linear search, and compared it to Rust’s builtin binary_search method. Source code is below.

I found linear search to outperform binary search on arrays of integers with
fewer than about 150 elements. Here’s a graph. Runtime is measured as the
*average wall clock time in ns taken to search through an array of the given
size*. Each run is performed a thousand times over a million arrays and
averaged to smooth out meaningless variation, though it’s still fairly bumpy.

You can see that the theory is born out quite well: linear search’s graph looks quite linear and binary search’s graph looks quite logarithmic.

March 1, 2020