//! 归并排序

pub fn sort<T:Copy + PartialOrd>(data:&mut Vec<T>){
	let n = data.len();
	merge_sort(data,0,n-1);
}

fn merge_sort<T:Copy + PartialOrd>(data:&mut Vec<T>,s:usize,t:usize){
	if s < t{
		let m = (s + t)/2;
		merge_sort(data,s,m);
		merge_sort(data,m+1,t);
		merge(data,s,m,t);
	}
}

fn merge<T:Copy + PartialOrd>(data:&mut Vec<T>,s:usize,m:usize,t:usize){
	let mut i = s;
	let mut j = m + 1;
	let mut temp = Vec::new();
	loop{
		if i > m || j > t{
			break;
		}
		if data[i] < data[j]{
			temp.push(data[i]);
			i += 1;
		}else{
			temp.push(data[j]);
			j += 1;
		}
	}
	loop{
		if i > m{
			break;
		}
		temp.push(data[i]);
		i += 1;
	}
	loop{
		if j > t{
			break;
		}
		temp.push(data[j]);
		j += 1;
	}
	let mut start = s;
	for d in temp{
		data[start] = d;
		start += 1;
	}
}

