Function insertion_sort 

pub fn insertion_sort<T: Ord>(arr: &mut [T])

Insertion sort — qo’lingizdagi kartalarni terganingizdek.

G’oya: chap tomon har doim tartiblangan. Navbatdagi elementni olib, chapdagi tartiblangan qismning to’g’ri joyiga “suqib” qo’yamiz.

Amaliy ahamiyati katta: kichik massivlarda (n < 32) va deyarli tartiblangan ma’lumotlarda hamma narsadan tez. Shuning uchun TimSort/pdqsort ichida ishlatiladi.

• Time: O(n) (tartiblangan bo’lsa) / O(n²), Space: O(1), barqaror.

Misol

use rust_algorithms::sorting::insertion_sort;

let mut v = vec![12, 11, 13, 5, 6];
insertion_sort(&mut v);
assert_eq!(v, [5, 6, 11, 12, 13]);