pub fn insertion_sort(arr: &mut [i32])Expand description
Sorts a slice using the Insertion Sort algorithm.
Insertion sort builds the sorted array one element at a time. It takes each new element and inserts it into its correct position within the sorted portion of the array.
§Parameters
arr: A mutable reference to the slice of integers to be sorted.
§Time Complexity
- Best:
O(n) - Worst:
O(n²) - Average:
O(n²)
§Space Complexity
O(1)(in-place sorting)
§Examples
use dsa::algorithms::sorting::insertion_sort;
let mut arr = [5, 3, 8, 4, 2];
insertion_sort(&mut arr);
assert_eq!(arr, [2, 3, 4, 5, 8]);