Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. However, insertion sort provides several advantages: Simple implementation: Jon Bentley shows a three-line c version, and a five-line optimized version Efficient for (quite) small data sets, much like other quadratic sorting algorithmsAdaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each component in the input is no more than K places away from its sorted position Stable; i.e., makes not change the relative order of components with equal keys

To perform an insertion sort, begin at the left-most component of the array and invoke insert to insert each component encountered into its correct position. It operates by beginning at the end of the sequence and shifting each component one place to the right until a suitable position is found for the new component.

```
use std::cmp;
#[allow(dead_code)]
pub fn insertion_sort<T>(arr: &[T]) -> Vec<T>
where
T: cmp::PartialEq + cmp::PartialOrd + Clone,
{
// The resulting vector should contain the same amount of elements as
// the slice that is being sorted, so enough room is preallocated
let mut result: Vec<T> = Vec::with_capacity(arr.len());
// Iterate over the elements to sort and
// put a clone of the element to insert in elem.
for elem in arr.iter().cloned() {
// How many elements have already been inserted?
let n_inserted = result.len();
// Loop over the inserted elements and one more index.
for i in 0..=n_inserted {
// If at the end or result[i] is larger than the current element,
// we have found the right spot:
if i == n_inserted || result[i] > elem {
// Insert the element at i,
// move the rest to higher indexes:
result.insert(i, elem);
break;
}
}
}
result
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn empty() {
let res = insertion_sort(&Vec::<u8>::new());
assert_eq!(res, vec![]);
}
#[test]
fn one_element() {
let res = insertion_sort(&vec!["a"]);
assert_eq!(res, vec!["a"]);
}
#[test]
fn already_sorted() {
let res = insertion_sort(&vec!["a", "b", "c"]);
assert_eq!(res, vec!["a", "b", "c"]);
}
#[test]
fn basic() {
let res = insertion_sort(&vec!["d", "a", "c", "b"]);
assert_eq!(res, vec!["a", "b", "c", "d"]);
}
#[test]
fn odd_number_of_elements() {
let res = insertion_sort(&vec!["d", "a", "c", "e", "b"]);
assert_eq!(res, vec!["a", "b", "c", "d", "e"]);
}
#[test]
fn repeated_elements() {
let res = insertion_sort(&vec![542, 542, 542, 542]);
assert_eq!(res, vec![542, 542, 542, 542]);
}
}
```