Linear search is faster than binary search for integer arrays with less than
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
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
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.