Function shell_sort 

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

Shell sort — insertion sortning “uzoq masofaga sakraydigan” versiyasi.

G’oya: avval bir-biridan gap masofada turgan elementlarni tartiblaymiz, keyin gap ni kichraytira boramiz. Katta gaplar elementlarni tez o’z hududiga olib keladi, oxirgi gap = 1 esa deyarli tayyor massivni tugatadi.

Bu yerda Knuth ketma-ketligi ishlatilgan: 1, 4, 13, 40, 121… (3h+1).

• Time: ~O(n^1.3) amalda, Space: O(1), barqaror emas.

Misol

use rust_algorithms::sorting::shell_sort;

let mut v = vec![23, 12, 1, 8, 34, 54, 2, 3];
shell_sort(&mut v);
assert_eq!(v, [1, 2, 3, 8, 12, 23, 34, 54]);