liveBook · Manning

Insertion sort

Insertion sort is a comparison-sorting algorithm that builds a sorted sequence by inserting each successive element into its proper position among the elements already sorted.

How 2 Manning books explain it

Type-Driven Development with Idris

A sorting algorithm that builds a sorted sequence by inserting each element into its correct position in the already-sorted portion.

How it is used
Uses insertion sort to demonstrate interactive, type-driven development of a vector-sorting function.
How deep it goes
Works through recursive sorting and insertion, while the function's type specifies length preservation rather than sortedness.
Examples
Sorts a nine-element integer vector and inspects its result in the REPL.
What you can do after
Build it from scratch in Idris using a recursive insertion helper and interactive type-driven refinement.

Read how Type-Driven Development with Idris explains insertion sort →

CUDA for LLMs

Insertion sort orders items by inserting each item into its proper position in a previously ordered subset.

How it is used
Selects top-k expert scores for MoE routing by maintaining a sorted buffer as scores are scanned.
How deep it goes
Traces buffer initialization, comparison, shifting, and insertion, then compares complexity and overhead with parallel alternatives.
Examples
Uses a case with 8 experts and k = 2, requiring 16 comparisons.
What you can do after
Build it from scratch to maintain sorted values and indices while scanning a small top-k input.

Read how CUDA for LLMs explains insertion sort →

Also covered in

Related concepts

Questions about insertion sort

What is insertion sort?

Insertion sort is a comparison-sorting algorithm that builds a sorted sequence by inserting each successive element into its proper position among the elements already sorted.

Which Manning books explain insertion sort?

Type-Driven Development with Idris and CUDA for LLMs.

What is the difference between insertion sort and reduction operation?

Insertion sort is a comparison-sorting algorithm that builds a sorted sequence by inserting each successive element into its proper position among the elements already sorted. A reduction operation combines multiple input values according to a rule to produce fewer results, often a single aggregate.

What is insertion sort a kind of?

Insertion sort is a kind of machine learning. Machine learning is a field of computational methods in which systems learn patterns or relationships from data to make predictions, decisions, or other outputs.

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.