Function merge_sort 

pub fn merge_sort<T: Ord + Clone>(arr: &mut [T])

Merge sort — “bo’l va hukmronlik qil” (divide & conquer) ning etaloni.

G’oya (3 qadam):

1. Massivni ikkiga bo’lamiz;
2. Har ikkala yarmini rekursiv tartiblaymiz;
3. Ikki tartiblangan yarmni bitta tartiblangan massivga qo’shamiz (merge).

Merge qadami chiziqli: ikkala yarmning boshiga barmoq qo’yib, kichigini olaveramiz.

• Time: O(n log n) — har doim (kirishga bog’liq emas).
• Space: O(n) — vaqtinchalik bufer.
• Barqaror: ha (<= sharti tufayli chapdagi element birinchi olinadi).

Misol

use rust_algorithms::sorting::merge_sort;

let mut v = vec![38, 27, 43, 3, 9, 82, 10];
merge_sort(&mut v);
assert_eq!(v, [3, 9, 10, 27, 38, 43, 82]);