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.
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.
Also covered in
- Algorithms Every Programmer Should KnowIn early access (MEAP)
- Grokking Data Structures
Related concepts
- top-kused by · Top-k is a selection operation that retains the k items ranked highest according to a specified value or criterion.
- machine learningkind of · Machine learning is a field of computational methods in which systems learn patterns or relationships from data to make predictions, decisions, or other outputs.
- reduction operationalternative to · A reduction operation combines multiple input values according to a rule to produce fewer results, often a single aggregate.
- sorting algorithmaddresses · A sorting algorithm is a procedure that rearranges elements of a collection into an order determined by an ordering criterion.
- bubble upequivalent to · Bubble up is a heap-repair technique that moves an element toward the root until the heap-ordering property is restored.
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.

