//! 希尔排序（缩小增量排序）

pub fn sort<T:Copy + PartialOrd>(data:&mut Vec<T>){
	let n = data.len();
	let mut k = n;
	let mut delta = Vec::new();
	loop{
		k = k/2;
		delta.push(k);
		if k <= 1{
			break;
		}
	}
	for dk in delta{
		for k in dk..n{
			let t = data[k];
			let mut j:isize = k as isize - dk as isize;
			loop{
				if j < 0 || t >= data[j as usize]{
					break;
				}
				data[j as usize+dk] = data[j as usize];
				j -= dk as isize;
			}
			data[(j+dk as isize) as usize] = t;
		}
	}
}
