Optimal Filter Search Sort List

A problem I’ve been seeing frequently at work is a list of items on the frontend that is filterable, sortable, and searchable.

There should be an optimal order for these three operations.

Testing a few combinations:

1_000_000 Items

1. Filter: 'red'
2. Sort by: 'A-Z'
3. Search: 'a'
Time: 86ms

1. Sort by: 'A-Z'
2. Search: 'a'
3. Filter: 'red'
Time: 220ms

1. Sort by: 'A-Z'
2. Filter: 'red'
3. Search: 'a'
Time: 229ms

1. Filter: 'red'
2. Search: 'a'
3. Sort by: 'A-Z'
Time: 61ms

These results aren’t too surprising. Sorting first provides the longest time at around 225ms while sorting last is fastest at around 60ms. Quick Sort is O(n log n) which is much longer than the O(n) filtering on a single color. Searching a string is naively an O(m * n) operation but can also be as fast as O(n).

Taking these into account, we want to reduce the size of the list by as much as possible before sorting. We could even combine filtering and searching in the same loop.

So the order of operations is:

1. Filter - always O(n) since the number of filter options is generally pre-defined
2. Search - as fast as O(n)
3. Sort - O(n log n) pretty slow considering the other contenders.

Probably the most interesting part of these results is that if you mess up the order and sort first, the entire operation would take almost 4x as long as if you sorted last.