sorting_algorithm/
insertion_sort.rs

1/// Sorts a data set using Insertion Sort
2///
3/// Average time complexity: O(n<sup>2<sup>)
4///
5/// # Examples
6///
7/// ```
8/// use sorting_algorithm::insertion_sort;
9///
10/// fn main() {
11///     let mut data = [3, 1, 2, 5, 4];
12///     
13///     insertion_sort::sort(&mut data);
14///
15///     assert_eq!(data, [1, 2, 3, 4, 5]);
16/// }
17/// ```
18pub fn sort<T: Ord>(data: &mut [T]) {
19    for i in 1..data.len() {
20        let mut j = i;
21
22        while j > 0 && data[j] < data[j - 1] {
23            data.swap(j, j - 1);
24            j -= 1;
25        }
26    }
27}