Tags: web-dev concept

Sorting and Searching

Date: 2026-08-17

---

The handful worth understanding, and the strong reason you’ll never write one. What matters in practice is knowing what the built-in guarantees — stability, complexity, and what it does to your data before you look.

---

Sorting puts elements in order by a comparison. Searching finds an element. Every language ships good implementations of both, so the useful knowledge is about their properties, not their code.

The three sorts worth recognising

MERGE SORT      O(n log n) always
  stable, predictable, needs O(n) space
  the safe default

QUICKSORT       O(n log n) average
                O(n²) worst
  in-place, fast in practice
  worst case is a pathological pivot

HEAPSORT        O(n log n) always
  in-place, not stable, slower constants

Real implementations are hybrids. Most runtimes use a mix — quicksort or a variant for the bulk, insertion sort for small partitions, with a fallback if recursion goes too deep. You get O(n log n) with good constants and no worst-case cliff.

Stability, which is the property that bites

A stable sort preserves the original relative order of equal elements.

sort by PRICE, then by NAME

UNSTABLE                 STABLE
Apple   £5               Apple   £5
Cherry  £5               Banana  £5
Banana  £5               Cherry  £5
  ↑ equal prices in       ↑ still alphabetical
    arbitrary order         within equal prices

This is why multi-column sorting works at all: sort by the secondary key first, then by the primary key with a stable sort, and the secondary ordering survives. With an unstable sort, it doesn’t, and the bug looks like “the list order is random sometimes”.

[CHECK: whether your runtime’s sort is guaranteed stable — this has changed between JavaScript engine versions and differs across languages.]

The two searches

LINEAR SEARCH        O(n)
  works on anything
  no precondition

BINARY SEARCH        O(log n)
  requires SORTED input
  halve the range each step

find 37 in a sorted array of 1,000,000

linear   up to 1,000,000 comparisons
binary   20 comparisons

Binary search’s precondition is the whole story. On unsorted data it doesn’t fail loudly — it returns the wrong answer. And sorting to enable one search costs O(n log n), which is worse than just scanning. Sort once, search many times, or don’t sort at all.

What you’ll actually do instead

For anything repeated, build a lookup structure rather than searching:

one search        linear scan, fine
many searches     Map or Set — O(1) each
range queries     sorted array + binary
                  search, or a tree

That’s the same reasoning a database uses when it builds an index — Indexing, Data Structures.

Practical traps

• JavaScript’s default sort is lexicographic, even on numbers. [10, 9, 1].sort() gives [1, 10, 9]. Always pass a comparator
• Sorting mutates in place in most languages, including JavaScript. If something else holds a reference to that array, you’ve just reordered their data too — Immutability
• Comparator must be consistent. A comparator that isn’t transitive, or that returns inconsistent results for the same pair, produces undefined behaviour rather than an error
• Locale-aware comparison is not the same as byte comparison. Sorting names or product titles needs Intl.Collator or its equivalent, or “Émile” sorts after “Zoë” — Character Encoding
• Sort in the database where you can. It has indexes, more memory, and does not need to ship the data to you first — Query Planning

The honest summary

You need to know: is it stable, what’s the comparator, and am I sorting when I should be indexing. Everything else is the runtime’s problem.