Skip to main content

merge

competitive::algorithm::sort

Function merge 

Source 
unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &mut F)
where
    F: FnMut(&T, &T) -> bool,
Examples found in repository?
crates/competitive/src/algorithm/sort.rs (lines 257-262)
236fn merge_sort<T, F>(v: &mut [T], mut is_less: F)
237where
238    F: FnMut(&T, &T) -> bool,
239{
240    let len = v.len();
241    if len <= 1 {
242        return;
243    }
244    let mut buf = Vec::with_capacity(len / 2);
245    let mut runs: Vec<Run> = vec![];
246    let mut end = len;
247    while end > 0 {
248        let start = end - 1;
249        let mut left = Run {
250            start,
251            len: end - start,
252        };
253        end = start;
254
255        while let Some(right) = runs.pop_if(|right| left.start == 0 || right.len <= left.len) {
256            unsafe {
257                merge(
258                    &mut v[left.start..right.start + right.len],
259                    left.len,
260                    buf.as_mut_ptr(),
261                    &mut is_less,
262                );
263            }
264            left = Run {
265                start: left.start,
266                len: left.len + right.len,
267            };
268        }
269        runs.push(left);
270    }
271
272    debug_assert!(runs.len() == 1 && runs[0].start == 0 && runs[0].len == len);
273
274    #[derive(Clone, Copy)]
275    struct Run {
276        start: usize,
277        len: usize,
278    }
279}