Method merge

publication/code/chapter07/tim_sort.rs:224–282

归并排序

(&mut self)

    // 归并排序
    unsafe fn merge(&mut self) {
        let mut first_count = 0;
        let mut second_count = 0;
        while self.second_pos > self.dest_pos && self.second_pos < self.list_len {
            debug_assert!(self.first_pos + (self.second_pos - self.first_len) == self.dest_pos);
            if (second_count | first_count) < MIN_GALLOP {
                if self.temp.get_unchecked(self.first_pos) > self.list.get_unchecked(self.second_pos) {
                    ptr::copy_nonoverlapping(
                        self.list.get_unchecked(self.second_pos),
                        self.list.get_unchecked_mut(self.dest_pos),
                        1,
                    );
                    self.second_pos += 1;
                    second_count += 1;
                    first_count = 0;
                } else {
                    ptr::copy_nonoverlapping(
                        self.temp.get_unchecked(self.first_pos),
                        self.list.get_unchecked_mut(self.dest_pos),
                        1,
                    );
                    self.first_pos += 1;
                    first_count += 1;
                    second_count = 0;
                }
                self.dest_pos += 1;
            } else {
                // Galloping 加速模式
                second_count = gallop_left(
                    self.temp.get_unchecked(self.first_pos),
                    self.list.split_at(self.second_pos).1,
                    Mode::Forward,
                );
                ptr::copy(
                    self.list.get_unchecked(self.second_pos),
                    self.list.get_unchecked_mut(self.dest_pos),
                    second_count,
                );
                self.dest_pos += second_count;
                self.second_pos += second_count;

                debug_assert!(self.first_pos + (self.second_pos - self.first_len) == self.dest_pos);
                if self.second_pos > self.dest_pos && self.second_pos < self.list_len {
                    first_count = gallop_right(
                        self.list.get_unchecked(self.second_pos),
                        self.temp.split_at(self.first_pos).1,
                        Mode::Forward,
                    );
                    ptr::copy_nonoverlapping(
                        self.temp.get_unchecked(self.first_pos),
                        self.list.get_unchecked_mut(self.dest_pos),
                        first_count,
                    );
                    self.dest_pos += first_count;
                    self.first_pos += first_count;
                }
            }
        }