# Algorithm

> Algorithms and data structures, explained in plain words, proved by hand and in Lean, implemented and tested in many languages, and shown step by step.

Each page has a Markdown copy at /<slug>.md and a JSON record at /<slug>.json. The list of every page is at /api/nodes.json. The text is CC BY-SA 4.0. The code is MIT.

## Problems

- [Search in a sorted array](https://algorithm.tamnd.com/search-in-sorted-array.md): Given a sorted array and a key, find an index of the key, or report that the key is not in the array.
- [Sorting](https://algorithm.tamnd.com/sorting-problem.md): Put the items of a sequence in non-decreasing order by a key.

## Algorithms

- [Binary search](https://algorithm.tamnd.com/binary-search.md): Find a key in a sorted array. Compare the key with the middle item, and keep only the half that can hold the key.
- [Insertion sort](https://algorithm.tamnd.com/insertion-sort.md): Sort an array one item at a time. Take the next item and move it left until the item before it is not larger.
- [Merge sort](https://algorithm.tamnd.com/merge-sort.md): Sort an array by divide and conquer. Sort each half, then merge the two sorted halves into one sorted array.

## Concepts

- [Loop invariant](https://algorithm.tamnd.com/loop-invariant.md): A statement about the variables of a loop that is true before each step. It is the main tool to prove that a loop is correct.

## Definitions

- [Asymptotic notation](https://algorithm.tamnd.com/asymptotic-notation.md): The notations O, Ω and Θ compare the growth of two functions for large inputs and ignore constant factors.

## Models

- [Comparison model](https://algorithm.tamnd.com/comparison-model.md): A model where an algorithm learns about its input only by comparing two items. The cost is the number of comparisons.