Sorting Algorithms — Brief ☧

Deep version → | Related: Big-O → | Flashcards →

Q: Matthew 1:17 records: "So all the generations from Abraham to

David are fourteen generations; and from David until the carrying away

into Babylon are fourteen generations; and from the carrying away into

Babylon unto Christ are fourteen generations." The genealogy is in

order. Why does that matter?

A: Because order lets you find things fast. If the forty-two names

were scattered randomly on a scroll, finding whether David appears

would mean reading every name —

O(N). But because they are

arranged from earliest ancestor to latest descendant, a scribe can use

binary search: open to the

middle, check whether David comes before or after, discard the wrong

half. That is O(log N). **Sorting

unlocks faster search.**

Q: So how would a scribe sort a pile of unsorted name scrolls?

A: He would need to compare names and swap those that are

out of place. This is the idea behind a comparison sort: look at

two items, decide which comes first, rearrange. The question is *how

many* comparisons are needed.

Q: What is the simplest approach?

A: Imagine the scribe passing through the pile over and over. Each

time, he compares neighboring scrolls and swaps any pair that is out of

order. After one pass, the last scroll is correct. After two passes, the

last two are correct. This is Bubble Sort. It works, but it is

slow: O(N squared). For 42

names, that could be up to 42 x 42 = 1,764 comparisons.

Q: Can we do better?

A: Much better. Consider this: the scribe divides the pile in half,

sorts each half separately (perhaps handing one half to an assistant),

then merges the two sorted halves together. Merging two sorted

sequences is easy — just compare the top of each pile and take the

smaller one. This is Merge Sort, and it runs in

O(N log N) time. That's the best any

comparison sort can do — a mathematical certainty.

Q: Why can't comparison sorts beat O(N log N)?

A: Because each comparison gives a yes-or-no answer (one bit of

information). With N items, there are N! (N factorial) possible

orderings. You need at least log(N!) comparisons to distinguish them

all, and log(N!) is proportional to N log N. No comparison-based

algorithm can escape this bound.

Q: Is there a way around the bound?

A: Yes — if you know something extra about the data. Suppose the

scribe knows every name corresponds to a generation number from 1 to

1. He lays out 42 slots on a long table and drops each scroll into its numbered slot. No comparisons needed. This is Counting Sort — it runs in O(N + K) time, where K is the range of values. When K is small, this is effectively linear.

Q: How do you choose which sorting

algorithm to use?

A: It depends on the situation:

• Merge Sort when you need guaranteed O(N log N) and stability (equal elements keep their original order).
• Quicksort when you want fast average-case performance and in-place sorting (no extra memory). But watch out: its worst case is O(N squared) if the pivot choices are unlucky.
• Counting / Radix Sort when values have a known, bounded range.

The Key Algorithms

When choosing among these algorithms, the situation dictates the tool. For small or nearly-sorted data, even the simple approaches work well. For large datasets, O(N log N) algorithms like Merge Sort and Quicksort are the standard workhorses. And when you have the luxury of bounded integer values, Counting Sort and Radix Sort bypass comparison entirely to achieve linear time.

Connection to our FPGA: Sorting determines contraction order for tensor operations. Our hardware uses fixed-order scheduling, but the offline optimizer that chooses which domains to process first relies on efficient sorting of cost estimates. The M6B scheduler also bins commands by lane ID using a technique equivalent to counting sort, since lane IDs are small integers (0 through 7).

Learn more in the deep version

Related: Big-O Notation | Trees

Graphs	Hash Tables

Soli Deo Gloria