// slice. Partition the slice into elements equal to and elements greater than the pivot.

// This case is usually hit when the slice contains many duplicate elements.

if let Some(p) = ancestor_pivot {

if !is_less(p, unsafe { v.get_unchecked(pivot_pos) }) {

// SAFETY: choose_pivot promises to return a valid pivot position.

let pivot = unsafe { v.get_unchecked(pivot_pos) };

if !is_less(p, pivot) {

let num_lt = partition(v, pivot_pos, &mut |a, b| !is_less(b, a));

// Continue sorting elements greater than the pivot. We know that `mid` contains

fn small_sort_general<T: FreezeMarker, F: FnMut(&T, &T) -> bool>(v: &mut [T], is_less: &mut F) {

let mut stack_array = MaybeUninit::<[T; SMALL_SORT_GENERAL_SCRATCH_LEN]>::uninit();

// SAFETY: The memory is backed by `stack_array`, and the operation is safe as long as the len

// is the same.

let scratch = unsafe {

slice::from_raw_parts_mut(

stack_array.as_mut_ptr() as *mut MaybeUninit<T>,

}

// SAFETY: The right side of `v` based on `len_div_2` is guaranteed in-bounds.

region =

unsafe { &mut *ptr::slice_from_raw_parts_mut(v_base.add(len_div_2), len - len_div_2) };

unsafe {

region = &mut *ptr::slice_from_raw_parts_mut(v_base.add(len_div_2), len - len_div_2)

};

}

// SAFETY: We checked that T is Freeze and thus observation safe.

mem::size_of::<T>() <= 8 // mem::size_of::<u64>()

}

#[test]

fn type_info() {

assert!(has_efficient_in_place_swap::<i32>());

assert!(has_efficient_in_place_swap::<u64>());

assert!(!has_efficient_in_place_swap::<u128>());

assert!(!has_efficient_in_place_swap::<String>());

}

/// SAFETY: Only used for run-time optimization heuristic.

#[rustc_unsafe_specialization_marker]

trait CopyMarker {}

// Otherwise a type like Mutex<Option<Box<str>>> could lead to double free.

!T::is_freeze()

}

#[test]

fn freeze_check() {

assert!(!has_direct_interior_mutability::<u32>());

assert!(!has_direct_interior_mutability::<[u128; 2]>());

assert!(has_direct_interior_mutability::<crate::cell::Cell<u32>>());

assert!(has_direct_interior_mutability::<crate::sync::Mutex<u32>>());

}

impl<T> Drop for GapGuard<T> {

fn drop(&mut self) {

// SAFETY: `self` MUST be constructed in a way that makes copying the gap value into

// `self.pos` sound.

unsafe {

ptr::copy_nonoverlapping(&*self.value, self.pos, 1);

}

impl<T> Drop for GapGuardRaw<T> {

fn drop(&mut self) {

// SAFETY: `self` MUST be constructed in a way that makes copying the gap value into

// `self.pos` sound.

unsafe {

ptr::copy_nonoverlapping(self.value, self.pos, 1);

}

#[test]

#[cfg(not(target_arch = "wasm32"))]

fn sort_unstable() {

// use core::cmp::Ordering::{Equal, Greater, Less};

use rand::Rng;

// Miri is too slow (but still need to `chain` to make the types match)