How Rust's 2016 merge sort uses natural runs

fn merge_sort<T, F>(v: &mut [T], mut compare: F)
    where F: FnMut(&T, &T) -> Ordering
{
    let (max_insertion, min_run) = if size_of::<T>() <= 16 {
        (64, 32)
    } else {
        (32, 16)
    };

    let len = v.len();

    let mut buf = Vec::with_capacity(len / 2);
    let mut runs = vec![];
    let mut end = len;
    while end > 0 {
        // Find the next natural run, and reverse it if it's strictly descending.
        let mut start = end - 1;
        if start > 0 {
            start -= 1;
            if compare(&v[start], &v[start + 1]) == Greater {
                while start > 0 && compare(&v[start - 1], &v[start]) == Greater {
                    start -= 1;
                }
                v[start..end].reverse();
            } else {
                while start > 0 && compare(&v[start - 1], &v[start]) != Greater {
                    start -= 1;
                }
            }
        }

        // Insert some more elements into the run if it's too short. Insertion sort is faster than
        // merge sort on short sequences, so this significantly improves performance.
        while start > 0 && end - start < min_run {
            start -= 1;
            insert_head(&mut v[start..end], &mut compare);
        }

        // Push this run onto the stack.
        runs.push(Run {
            start: start,
            len: end - start,
        });
        end = start;

        // Merge some pairs of adjacent runs to satisfy the invariants.
        while let Some(r) = collapse(&runs) {
            let left = runs[r + 1];
            let right = runs[r];
            unsafe {
                merge(&mut v[left.start .. right.start + right.len], left.len, buf.as_mut_ptr(),
                      &mut compare);
            }
            runs[r] = Run {
                start: left.start,
                len: left.len + right.len,
            };
            runs.remove(r + 1);
        }
    }
    #[inline]
    fn collapse(runs: &[Run]) -> Option<usize> {
        let n = runs.len();
        if n >= 2 && (runs[n - 1].start == 0 ||
                      runs[n - 2].len <= runs[n - 1].len ||
                      (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len) ||
                      (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len)) {
            if n >= 3 && runs[n - 3].len < runs[n - 1].len {
                Some(n - 3)
            } else {
                Some(n - 2)
            }
        } else {
            None
        }
    }
}

fn insert_head<T, F>(v: &mut [T], compare: &mut F)
    where F: FnMut(&T, &T) -> Ordering
{
    if v.len() >= 2 && compare(&v[0], &v[1]) == Greater {
        unsafe {
            let mut tmp = NoDrop { value: ptr::read(&v[0]) };
            let mut hole = InsertionHole {
                src: &mut tmp.value,
                dest: &mut v[1],
            };
            ptr::copy_nonoverlapping(&v[1], &mut v[0], 1);

            for i in 2..v.len() {
                if compare(&tmp.value, &v[i]) != Greater {
                    break;
                }
                ptr::copy_nonoverlapping(&v[i], &mut v[i - 1], 1);
                hole.dest = &mut v[i];
            }
            // `hole` gets dropped and thus copies `tmp` into the remaining hole in `v`.
        }
    }
}

unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, compare: &mut F)
    where F: FnMut(&T, &T) -> Ordering
{
    let len = v.len();
    let v = v.as_mut_ptr();
    let v_mid = v.offset(mid as isize);
    let v_end = v.offset(len as isize);
    let mut hole;

    if mid <= len - mid {
        // The left run is shorter.
        ptr::copy_nonoverlapping(v, buf, mid);
        hole = MergeHole {
            start: buf,
            end: buf.offset(mid as isize),
            dest: v,
        };

        // Initially, these pointers point to the beginnings of their arrays.
        let left = &mut hole.start;
        let mut right = v_mid;
        let out = &mut hole.dest;

        while *left < hole.end && right < v_end {
            // Consume the lesser side.
            // If equal, prefer the left run to maintain stability.
            let to_copy = if compare(&**left, &*right) == Greater {
                get_and_increment(&mut right)
            } else {
                get_and_increment(left)
            };
            ptr::copy_nonoverlapping(to_copy, get_and_increment(out), 1);
        }
    } else {
        // The right run is shorter.
        ptr::copy_nonoverlapping(v_mid, buf, len - mid);
        hole = MergeHole {
            start: buf,
            end: buf.offset((len - mid) as isize),
            dest: v_mid,
        };

        // Initially, these pointers point past the ends of their arrays.
        let left = &mut hole.dest;
        let right = &mut hole.end;
        let mut out = v_end;

        while v < *left && buf < *right {
            // Consume the greater side.
            // If equal, prefer the right run to maintain stability.
            let to_copy = if compare(&*left.offset(-1), &*right.offset(-1)) == Greater {
                decrement_and_get(left)
            } else {
                decrement_and_get(right)
            };
            ptr::copy_nonoverlapping(to_copy, decrement_and_get(&mut out), 1);
        }
    }
    // Finally, `hole` gets dropped. If the shorter run was not fully consumed, whatever remains of
    // it will now be copied into the hole in `v`.
}