File InsertionSort.h

↰ Parent directory (ADS/sort)

Insertion Sort (section 2.7.2), as one sorts a hand of cards: A[ i ] is inserted in the sorted prefix A[ 0 .

Definition (ADS/sort/InsertionSort.h)

Detailed Description

. i - 1 ], the larger items moving one place to the right. :math:` Theta( n ) ` time on a sorted vector, :math:` Theta( n^2 ) ` on a reversed one and on average (n ( n - 1 ) / 4 moves), O( 1 ) space, stable; with its simple inner loop it is the fastest on few items, hence the base case of the hybrid sorts.

The contracts [see File Contract.h]: lo <= hi <= n, and the range ends sorted with the same items, an audit. The functions are defined in InsertionSort.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 2.7.2, https://algoritmicamente.it/materiali/libro/capitoli/cap02.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions